As a first step towards a solution, using the identity
$$\int_{\mathcal{U}(N)} U^{\vphantom{\ast}}_{\alpha a}U^{\vphantom{\ast}}_{\alpha' a'}U^{\ast}_{\beta b}U^{\ast}_{\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)}\left(|{\rm tr}\,A|^2+{\rm tr}\,AA^\dagger\right).$$

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