I do not get the argument why the chain rule is invalid. You can in fact proceed using the chain rule. For such questions is it usually easiest to write everything out in components. So first, we need $\partial_{X_{mn}} \mathop{\rm tr}X^2 =\partial_{X_{mn}} X_{ij}X_{ji} = \delta_{mi} \delta_{nj} X_{ji}+ \delta_{mj} \delta_{ni} X_{ij} = 2 X_{nm}; $ here, we have assumed that all indices which appear twice are summed over and used the fact that $\partial_{X_{mn}} X_{ij} = \delta_{mi} \delta_{nj}$.
Next, we need $\begin{align}\partial_{(q_i)_j} X_{mn} &=\partial_{(q_i)_j} Q_{km} Q_{kl} A_{ln} =\partial_{(q_i)_j} (q_m)_k (q_l)_k A_{ln} = \delta_{im} \delta_{jk} (q_l)_k A_{ln} + \delta_{il} \delta_{jk} (q_m)_k A_{ln}\\ &=(q_l)_j A_{ln} +(q_m)_j A_{in}\\ &= Q_{jl} A_{ln} + Q_{jm} A_{in} \end{align}$ because $Q_{mn} = (q_n)_m$.
In conclusion, we have $\begin{align}\partial_{(q_i)_j} \mathop{\rm tr}(Q^TQAQ^TQA) &= \partial_{X_{mn}} \mathop{\rm tr}X^2 \partial_{(q_i)_j} X_{mn} = 2 X_{mn} [ Q_{jl} A_{ln} + Q_{jm} A_{in}]\\ &= 2 Q_{km} Q_{kl} A_{ln}^2 Q_{jl} + 2Q_{jm} Q_{km} Q_{kl} A_{ln} A_{in}\\ &= 2(Q Q^T Q B \mathop{\rm tr} (A A^T) + Q Q^T Q A A^T)_{ji} \end{align}$ with $(B)_{ij}= 1$ the constant unit matrix.