As a first step towards a solution, using the identity
$$\int_{\mathcal{U}(N)} U_{\alpha a}U_{\alpha' a'}\bar{U}_{\beta b}\bar{U}_{\beta' b'}\,dU=\frac{1}{N^{2}-1}\bigl( \delta_{\alpha\beta}\delta_{ab}\delta_{\alpha'\beta'}\delta_{a'b'}+ \delta_{\alpha\beta'}\delta_{ab'}\delta_{\alpha'\beta}\delta_{a'b}\bigr)$$
$$\qquad\qquad\mbox{}-\frac{1}{N(N^{2}-1)}\bigl( \delta_{\alpha\beta}\delta_{ab'}\delta_{\alpha'\beta'}\delta_{a'b}+ \delta_{\alpha\beta'}\delta_{ab}\delta_{\alpha'\beta}\delta_{a'b'}\bigr),$$

I computed this integral for the trace,
$$\int_{\mathcal{U}(N)}{\rm tr}\, (AUA^\dagger U^\dagger)\,\overline{{\rm tr}\,(AUA^\dagger U^\dagger)}\,dU=\frac{1}{N^2-1}\left(|{\rm tr}\, A|^4+|{\rm tr}\,AA^\dagger|^2\right)-\frac{2}{N(N^2-1)}|{\rm tr}\,A|^2({\rm tr}\,AA^\dagger).$$

<sub>As a check, take $A=1$ and see that the right-hand-side reduces to $(N^4+N^2)/(N^2-1)-2N^3/(N^3-N)=N^2$.</sub>