  For any integer $m<n$, where $m$ can depend on $n$, we study the rate of
convergence of $\frac{1}{\sqrt{m}}\mathrm{Tr} \mathbf{U}^m$ to its limiting
Gaussian as $n\to\infty$ for orthogonal, unitary and symplectic Haar
distributed random matrices $\mathbf{U}$ of size $n$. In the unitary case, we
prove that the total variation distance is less than $\Gamma(\lfloor n/m
\rfloor+2)^{-1} m^{- \lfloor n/m\rfloor} \lfloor n/m \rfloor^{1/4}\sqrt{\log
n}$ times a constant. This result interpolates between the super-exponential
bound obtained for fixed $m$ and the $1/n$ bound coming from the Berry-Esseen
theorem applicable when $m\ge n$ by a result of Rains. We obtain analogous
results for the orthogonal and symplectic groups. In these cases, our total
variation upper bound takes the form $\Gamma(2\lfloor
n/m\rfloor+1)^{-1/2}m^{-\lfloor n/m\rfloor +1}(\log n)^{1/4}$ times a constant
and the result holds provided $n \geq 2m$. For $m=1$, we obtain complementary
lower bounds and precise asymptotics for the $L^2$-distances as $n\to\infty$,
which show how sharp our results are.
