Denote $(p-1)/2=n$ and replace the condition to $0\leqslant j<k\leqslant \frac{p-1}2$, this does not add new pairs satisfying $\{j(j+1)\}_p>\{k(k+1)\}_p$. Now denote $j=n-s$, $k=n-t$, we have $n\geqslant s>t\geqslant 0$ and our condition rewrites as $$\{(n-s)(n-s+1)\}_p>\{(n-t)(n-t+1)\}_p.$$
Note that $(n-s)(n-s+1)\equiv n(n+1)+s^2\equiv s^2-1/4$ modulo $p$. Denote $A=(p+1)/4$, then we have to count the number of pairs $s>t$ such that $\{s^2-A\}_p>\{t^2-A\}_p$. Note that in general
$$
{\rm sign}\, \left(\{s-A\}_p-\{t-A\}_p\right)={\rm sign}\, \left(\{s\}_p-\{t\}_p\right)\cdot (-1)^{\chi(\{s\}_p<A)+{\chi(\{t\}_p<A)}}.
$$
This observation reduces the sign we are interested in to two signs: 

at first, the product $\prod_{n\geqslant s>t\geqslant0}(\{s^2\}_p-\{t^2\}_p)$ which is your product $S_p$ from equation (1.4) in the cited paper;

at second, $(-1)^{M+1}$, where $M$ is the number of quadratic residues less than $(p+1)/4$.

The first guy is calculated by you, the second looks very classical. Namely, what remains to prove is the following:

if $p=8k+3$, then $(\frac{(2k)!}p)=(-1)^k$, that is, if the set $\{1,2,\dots,2k\}$ contains $k+x$ quadratic residues and $k-x$ quadratic non-residues, then $x$ is even;

if $p=8k+7$, the same holds for the set $\{2k,\dots,4k-1\}$, that is, 
$(\frac{(4k-1)!/(2k-1)!}p)=(-1)^k$.

That must be known and not hard.