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.