This is not a solution, rather it is a conjectured generalization of the claimed identity which may help in proving it:
The idea is to observe that $x^2$ is a primitive $n$-th root of unity, and to replace the factor $-x$ in $-x^{2j+1}=(-x)(x^2)^j$ with a new variable $z$.
Thus let $\zeta$ be a primitive $n$-th root of unity and $z$ be a variable. Then it seems to be the case that \begin{equation} \mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} \zeta^{-j} & \zeta^jz \\ 1 & 0 \end{pmatrix}\right)= \begin{cases} 3(1-\zeta^{n/6})z^{n/3}-1 & \text{if } n\equiv0\pmod{6}\\ 3(\zeta z)^{n/3} & \text{if } n\equiv3\pmod{6}\\ -(-1)^n & \text{if } n\not\equiv0,3\pmod{6} \end{cases}. \end{equation} Let $P(z)$ the term on the left hand side. It is clear that $P(z)$ is a polynomial in $z$ of degree at most $n-1$. Cyclically permuting the factors on the left hand side does not change the trace, and neither does conjugating each factor with the same matrix. Set $\delta=\zeta^k$ for some $0\le k\le n-1$. Then \begin{equation} \begin{pmatrix}1&0\\0&\delta\end{pmatrix} \begin{pmatrix}\zeta^{-j} & \zeta^jz \\1 & 0\end{pmatrix} \begin{pmatrix}1&0\\0&1/\delta\end{pmatrix} = \begin{pmatrix}\zeta^{-j} & \zeta^jz/\delta \\\delta & 0\end{pmatrix}= \delta\begin{pmatrix}\zeta^{-j-k} & \zeta^{j+k}(z\zeta^{-3k}) \\1 & 0\end{pmatrix}. \end{equation} This shows $P(z)=P(z\zeta^{3k})$ for all $0\le k\le n-1$.
So if $n\not\equiv0\pmod{3}$, then $P(z)$ must be a constant. One easily computes $P(0)$.
In the other cases, we only know that $P(z)$ is a polynomial in $z^{n/3}$ of degree less than $n$. I believe that a refinement of the argument should settle these cases too. For instance, besides the easy computation of $P(0)$, one could try to analyze $P(z)$ for $z\to\infty$.