Differences
A general useful fact (compare with my answer to your previous question) is that whenever we have $A=\{a_1,\dots,a_n\}\subset \{0,1,\dots,p-1\}$ such that $n=|A|$ is odd, the sign of a product $\prod_{i<j}(\{a_j-\theta\}_p-\{a_i-\theta\}_p)$ does not depend on the choice of remainder $\theta$ modulo $p$. This may be proved using the observation
$$
{\rm sign}\, \left(\{b-\theta\}_p-\{a-\theta\}_p\right)={\rm sign}\, \left(\{b\}_p-\{a\}_p\right)\cdot (-1)^{\chi(\{b\}_p<\theta)+\chi(\{a\}_p<\theta)}.
$$
When you multiply this by all pairs $b=a_j,a=a_i,i<j$, each multiple $(-1)^{\chi(\{a\}_p<\theta)}$ appears exactly $n-1$ times, which is even.
Now you take $n=(p-1)/2$, $a_j=T_{(p-1)/2-j}=\{-1/8+j^2/2\}_p$, $j$ varies from 0 to $(p-3)/2=n-1$ and you look for the sign of $\prod_{0\leqslant i<j\leqslant n-1} (a_i-a_j)$ (the order is inversed). This is the same as $$(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} (a_j-a_i)=(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} \left(\{j^2/2\}_p-\{i^2/2\}_p\right).$$
It is convenient to add $j=n$ and consider the product
$$
\prod_{0\leqslant i<j\leqslant n} \left(\{j^2/2\}_p-\{i^2/2\}_p\right).
$$
For finding its sign we exclude $i=0$ which does not rely on the sign and consider two cases.
1) $p$ is congruent to 7 modulo 8. In this case $2$ is a quadratic residue and the map $x\mapsto x/2$ permutes the (nonzero) quadratic residues. This permutation is even, because all cycles have the same odd length (dividing odd number $(p-1)/2$). On the other hand the sign of this permutation equals
$$
{\rm sign}\,\prod_{1\leqslant i<j\leqslant n} \frac{\{j^2/2\}_p-\{i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}.
$$
Therefore the numerator and the denominator have the same sign and we reduced the problem to the already solved in your paper.
2) $p=8k+3$. In this case -2 is a quadratic residue and we similarly get
$$
{\rm sign}\,\prod_{1\leqslant i<j\leqslant n} \frac{\{-j^2/2\}_p-\{-i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}=1.
$$
It remains to note that ${\rm sign}\, (\{j^2/2\}_p-\{i^2/2\}_p)=-{\rm sign}\, (\{-j^2/2\}_p-\{-i^2/2\}_p)$ (and mind the multiple $(-1)^{n\choose 2}$, but it equals 1 for $p=8k+3$, $n=4k+1$).
The last thing to do is to study what we have added: the sign of $\prod_{0\leqslant i<n}(\{n^2/2\}_p-\{i^2/2\}_p)$. We have $n^2/2\equiv 1/8$. Again consider two cases.
1) $p=8k+7$, then $1/8\equiv (p+1)/8$ and we look for the number of quadratic residues (recall that $i^2/2$ is a quadratic resdiue) greater than $(p+1)/8$. This has the parity different from that of the number of quadratic residues at most $(p+1)/8$ (since the total number of quadratic residues is odd.) But we had also a sign $(-1)^{n\choose 2}=-1$ before. So we get your conjecture in this case.
1) $p=8k+3$. Then $1/8\equiv (5p+1)/8$ and we look for the number of quadratic non-residues greater than $(5p+1)/8$. This is the same as the number of quadratic residues less than $(3p-1)/8$. The permutation of squares mod $p$ is even (proved in your paper), and $(-1)^{(h(-p)+1)/2}\equiv (4k+1)!$ has the same parity as the number of quadratic non-residues in $[1,p/2]$ (take Legendre symbol). Thus we should prove the following: the number of non-residues in $[1,4k+1]$ plus the number of residues in $[1,(3p-1)/8)$ plus the number of residues in $[1,p/8]$ is even. This rewrites as (Residues in $[1,p/2]$)+(Residues in $[1,3p/8]$)+(Residues in $[1,p/8]$) is even, or: (Residues in $[1,p/8]\cup [3p/8,p/2]$) is even. This is the statement of Berndt -- Chowla type. Consider all the quadratic non-residues in $(0,p/4)$ (there are $k$ of them by Berndt -- Chowla) and divide them by $2$. Even non-residues go to residues in $(0,p/8)$ and odd non-residues go to residues in $(p/2,5p/8)$ which correspond to non-residues in $(3p/8,p/2)$. Therefore we get $k=RES(0,p/8)+NONRES[3k+2,4k+1]=RES(0,p/8)+k-RES[3k+2,4k+1]$ and so the segments $[1,k]$ and $[3k+2,4k+1]$ simply have equally many quadratic residues.
This proves your conjecture for this case also.
Sums greater than $p$.
Let me concentrate here on the case $p=8k+1$. Other cases should be similar, let me know if they are not.
The idea is the following identity, in which we use the notation $\{\{a\}\}_p$ which equals $\{a\}_p$ whenever $\{a\}_p\ne 0$ and equals $p$ whenever $\{a\}_p=0$:
$$
\chi_{\{u\}_p+\{v\}_p>p}=\frac1p\left( \{u\}_p+\{v\}_p-\{\{u+v\}\}_p \right).\,\,\,\,(*)
$$
We take the set $T=\{T_0,T_1,\dots,T_{4k}\}$ (again I add $T_0$ but it does not affect to the parity we are interested in) and apply $(*)$ to all non-ordered pairs $(u,v)$ of different elements of $T$ and sum up. All guys $\{u\}_p$ go with coefficient $4k$, so do not affect on the parity. It remains to find the parity of the sum of $\{u+v\}_p$. Again use the representation $T_j=\frac12(j+\frac12)^2-\frac18$. When $j$ goes from 0 to $4k$, the expression $\frac12(j+\frac12)^2$ goes over the set $R_0$ consisting of quadratic residues and 0. Therefore $$f(a):=\left|(0\leqslant i<j\leqslant 4k):T_i+T_j\equiv a\right|=\\ \left|(0\leqslant i<j\leqslant 4k):i^2+j^2\equiv a+\frac14\right|=:g(a+\frac14).$$
And we are interested in the parity of $\sum_{j=0}^{p-1}\{\{j-\frac14\}\}_p g(j)$. Well, let's find $g(a)$ for any $a$, this is standard. We have $g(0)=2k$; $g(a)=k$ for $a$ not divisible by $p$. So we are interested in the parity of $$k\{\{-\frac14\}\}_p+k\sum_{j=0}^{p-1}\{\{j\}\}_p.$$
The first summand equals $k\cdot 2k$ and is even, the sum equals $1+2+\dots+p=p(p+1)/2$ and is odd, so totally the parity is the same as the parity of $k$.
