a simple and exact answer follows if $A$ is **a unitary $n\times n$ matrix**; then $\tilde{v}=Av$ is a unit vector and since $u$ is a randomly oriented unit vector the distribution of the scalar product $u^HAv=(u,\tilde{v})$ does not depend on the orientation of $\tilde{v}$, so we may take it in the $x_1$ direction, hence 

$$P(u^H Av)=P(u_1).$$

the distribution of a single element $u_1$ of the random unit vector $u$ follows upon integration over the other $n-1$ elements,

$$P(u_1)= \int du_2\int du_3\cdots\int du_n\;\delta\left(1-\sum_{i=1}^{n}|u_i|^2\right)={\rm constant}\times(1-|u_1|^2)^{n-2},$$ 

hence $\xi=|u^H Av|^2$ has the distribution

$$P(\xi)=(n-1)(1-\xi)^{n-2},\;\;0<\xi<1.$$

this is exact for any $n\geq 2$; for $n\gg 1$ the distribution becomes exponential to leading order in $1/n$,

$$P(\xi)\approx ne^{-n\xi}.$$

**for non unitary $A$,** the answer will depend on its singular values $a_1,a_2,\ldots a_n$; I doubt that you can find a simple closed-form expression for any $n$, but for $n\gg 1$ again an exponential distribution will appear.

To see this, define the unit vector $v'=|Av|^{-1}\,Av$ and first consider the distribution of $\xi'=|u^H v'|^2$. Here the same argument as above applies, so for $n\gg 1$ we have $P(\xi')\propto\exp(-n\xi')$. The quantity $\xi$ we want is related to $\xi'$ by $\xi=|Av|^2\xi'$. The factor $|Av|^2$ has a normal distribution in the large-$n$ limit, with a mean
$$E[|Av|^2]=\frac{1}{n}{\rm Tr}\,AA^H$$
and a variance that is an order $1/n$ smaller; to leading order in $1/n$ we may therefore just equate

$$\xi\approx E[Av|^2]\xi'\Rightarrow P(\xi)\approx\frac{n^2}{{\rm Tr}\,AA^H}\exp\left(-\frac{n^2}{{\rm Tr}\,AA^H}\xi\right).$$