Sign of permutation induced by modular exponentiation

Let $\varphi$ be an automorphism of the multiplicative group $\mathbb{F}_p^*$. Then $$x\sigma_{a,p}\varphi = (a^x)\varphi = (a\varphi)^x = x\sigma_{a\varphi, p}.$$ So the permutations $\sigma_{a,p}$ form a coset of the group of automorphisms of the cyclic group $\mathbb{F}_p^* \cong C_{p-1}$.

Now when $p-1=m=2u$ with $u$ odd, then $C_m = C_2 \times C_u$ and it is easy to see that every automorphism of $C_m$ is an even permutation. When $m$ is divisible by $4$, then the automorphism sending $c$ to $c^{-1}$ is odd, since it is a product of $(m-2)/2$ transpositions, and $(m-2)/2 $ is odd.

What I don't see just now is when one (and then all) $\sigma_{a,p}$ is odd or even in the case $p\equiv 3 \mod 4$.

Your second guess is also correct.

At first, we write down the sign of the permutation $\sigma_a$ as the product $\prod_{1\leqslant i<j\leqslant p-1}\frac{a^j-a^i}{j-i}$ modulo $p$. The denominator equals $(p-2)!(p-3)!\dots 1!$, and denoting $p=2m+1$ ($m$ is odd) we write it as $m!\prod_{j=1}^{m-1} j!(p-1-j)!=m!\prod_{j=1}^{m-1} (-1)^{j+1}=m!(-1)^{(m-1)/2}$. Here $m!$ appears, good.

Now for the numerator. We consider the polynomial $F(x)=\prod_{1\leqslant i<j\leqslant p-1} (x^j-x^i)$ modulo the cyclotomic polynomial $\Phi_{p-1}(x)$. We may write $F(x)=h(x)\Phi_{p-1}(x)+r(x)$ for polynomials $h,r$ with integer coefficients, $\deg r<\varphi(p-1)$, and of course $F(a)$ and $r(a)$ are congruent modulo $p$. So our goal is to find $r$. For this we substitute the complex root $\omega=e^{2\pi i/(p-1)}$ of $\Phi_{p-1}$ and get $r(\omega)=F(\omega)$. $F(\omega)$ may be calculated by the following (not original, in particular it is used for calculating the sign of Gauss sums) trick: at first, we know the argument of $F(\omega)$, since we know the argument $\frac\pi{2}+\frac\pi{2m}(k+j)$ of each bracket $\omega^k-\omega^j,1\leqslant j<k\leqslant p-1$, and they are easily summed up to $\pi(m-1)/2$ modulo $2\pi$. At second, we know $F^2(\omega)$. Indeed, using the formula $$\prod_{j\ne i} (\omega^i-\omega^j)={\frac{t^{p-1}-1}{t-\omega^i}}|_{t=\omega^i}=-(p-1)\omega^{-i},$$ the substitution is done by L'Hôpital rule; we get

$$ F^2(\omega)=-\prod_i\prod_{j\ne i} (\omega^i-\omega^j)=-(p-1)^{p-1}\omega^{-p(p-1)/2}=(p-1)^{p-1}. $$

Thus $r(\omega)=F(\omega)=(-1)^{(m-1)/2} (p-1)^{(p-1)/2}$, where the sign is obtained from the previously found argument of $F(\omega)$. Since $\deg r<\varphi(p-1)=\deg \Phi_{p-1}$ and $\Phi_{p-1}$ is irreducible, we conclude that $r=(-1)^{(m-1)/2} (p-1)^{(p-1)/2}$ identically and modulo $p$ we get $r(a)=(-1)^{(m+1)/2}$.

Thus totally the sign of $\sigma_a$ is $-m!$ modulo $p$.