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$.