T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$B_l=\{(i_1,...,i_k)\ |\ \text{ each } i_j\in\mathbb{N}\ \text{and}\ i_1 + ... + i_k = l \}$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=\binom{k+l-1}{l}$.