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)={\rm constant}\times(1-\xi)^{n-2},\;\;0<\xi<1.$$$$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).$$