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-1$, 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. Well, I did not find exactly the same fact, but something morally similar for $p=4k+1$ (in Yamamoto's paper "On Gaussian sums with biquadratic residue characters", Crelle 1965). Actually for $p=8k+3$ we always have equally many quadratic residues and non-residues in the set $\{1,2,\dots,2k\}$, the same for $p=8k-1$ and the set $\{2k,\dots,4k-1\}$.
The proof is simple as that. Let $p=8k+3$. Take all quadratic residues less than $p/2$. Some of them are odd and some are even. Divide them all by -2, we get quadratic residues again. The even quadratic residues transform to quadratic residues between $3p/4$ and $p$, the odd quadratic residues transform (by the map $x\mapsto (p-x)/2$) to quadratic residues between $p/4$ and $p/2$. Therefore we get the identity |residues(from 0 to $p/2$)|=|residues(from $3p/4$ to $p$)|+|residues(from $p/4$ to $p/2$)|. But the first sum is exactly |non-residues(from 0 to $p/4$)| (due to themap $x\mapsto p-x$) and we celebrate.
For $p=8k+7$ use 2 instead of -2.