3 deleted 18 characters in body

There is a method of explaining this without using analytic methods. I will get to that at the end of this answer.

First, if $p \equiv 1 \bmod 4$ then this result is clear since -1 is a square mod $p$. So here exactly half the squares mod $p$ lie in the first half of $[1,p-1]$. The real problem is for $p \equiv 3 \bmod 4$, where analytic methods show there are more squares mod $p$ lying in the first half of that interval than in the second half because there is a formula for the class number of ${\mathbf Q}(\sqrt{-p})$ that is 1 or 1/3 times $S - N$, where $S$ is the number of squares mod $p$ in $[1,(p-1)/2]$ and $N$ is the number of nonsquares mod $p$ in $[1,(p-1)/2]$. Class numbers are positive integers, so $S > N$, which means in $[1,(p-1)/2]$ the squares mod $p$ outnumber nonsquares mod $p$. Since there are as many squares as nonsquares mod $p$ on $[1,p-1]$, the square vs. nonsquare bias on the first half of this interval forces there to be more squares mod $p$ on the first half than squares mod $p$ on the second half.

For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is not true that no non-analytic derivations of this bias are known. For instance, Borevich and Shafarevich say on p. 347 that Venkov gave a non-analytic proof for some cases in 1928 (which came out in German in 1931: see Math Z. Vol. 33, 350--374). I should clarify this point since there is a bad typo in Borevich and Shafarevich here. What Venkov did was give a non-analytic proof of Dirichlet's class number formula for imaginary quadratic fields having discriminant $D \not\equiv 1 \bmod 8$. Here Borevich and Shafarevich the book unfortunately write has $D \equiv 1 \bmod 8$. (It's clear in their from the book that something is wrong because shortly after saying Venkov treated $D \equiv 1 \bmod 8$ by non-analytic methods they say the case $D \equiv 1 \bmod 8$ still awaits a non-analytic proof.) The class number formula only gets an interpretation about squares or nonsquares for the fields ${\mathbf Q}(\sqrt{-p})$, but Venkov was working on non-analytic proofs of the class number formula for imaginary quadratic fields without having this restrictive case as the only one in mind. R. W. Davis (Crelle 286/287 (1976), 369--379) made simplifications to Venkov's argument.

What cases for ${\mathbf Q}(\sqrt{-p})$ are covered by Venkov? When $p \equiv 3 \bmod 4$, the discriminant of ${\mathbf Q}(\sqrt{-p})$ is $-p$. If $p \equiv 3 \bmod 8$ then $-p \equiv 5 \bmod 8$, while if $p \equiv 7 \bmod 8$ then $-p \equiv 1 \bmod 8$, so Venkov had non-analytically proved the formula when $p \equiv 3 \bmod 8$. The case $p \equiv 7 \bmod 8$ remained open.

In 1978 the whole problem was solved. Davis, in a second paper (Crelle 299/300 (1978), 247--255), handled some but not all cases of imaginary quadratic fields with discriminant $1 \bmod 8$ (corresponding to $p \equiv 7 \bmod 8$ for the fields ${\mathbf Q}(\sqrt{-p})$) by non-analytic methods and in the same year H. L. S. Orde settled everything by non-analytic methods. See his paper "On Dirichlet's class number formula", J. London Math. Soc. 18 (1978), 409--420.

2 added 121 characters in body

There is a method of explaining this without using analytic methods. I will get to that at the end of this answer.

First, if $p \equiv 1 \bmod 4$ then this result is clear since -1 is a square mod $p$. So here exactly half the squares mod $p$ lie in the first half of $[1,p-1]$. The real problem is for $p \equiv 3 \bmod 4$, where analytic methods show there are more squares mod $p$ lying in the first half of that interval than in the second half because there is a formula for the class number of ${\mathbf Q}(\sqrt{-p})$ that is 1 or 1/3 times $S - N$, where $S$ is the number of squares mod $p$ in $[1,(p-1)/2]$ and $N$ is the number of nonsquares mod $p$ in $[1,(p-1)/2]$. Class numbers are positive integers, so $S > N$, which means in $[1,(p-1)/2]$ the squares mod $p$ outnumber nonsquares mod $p$. Since there are as many squares as nonsquares mod $p$ on $[1,p-1]$, the square vs. nonsquare bias on the first half of this interval forces there to be more squares mod $p$ on the first half than squares mod $p$ on the second half.

For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is not true that no non-analytic derivations of this bias are known. For instance, Borevich and Shafarevich say on p. 347 that Venkov gave a non-analytic proof for some cases in 1928 (which came out in German in 1931: see Math Z. Vol. 33, 350--374). I should clarify this point since there is a bad typo in Borevich and Shafarevich here. What Venkov did was give a non-analytic proof of Dirichlet's class number formula for imaginary quadratic fields having discriminant $D \not\equiv 1 \bmod 8$. Here Borevich and Shafarevich unfortunately write $D \equiv 1 \bmod 8$. (It's clear in their book that something is wrong because shortly after saying Venkov treated $D \equiv 1 \bmod 8$ by non-analytic methods they say the case $D \equiv 1 \bmod 8$ still awaits a non-analytic proof.) The class number formula only gets an interpretation about squares or nonsquares for the fields ${\mathbf Q}(\sqrt{-p})$, but Venkov was working on non-analytic proofs of the class number formula for imaginary quadratic fields without having this restrictive case as the only one in mind. R. W. Davis (Crelle 286/287 (1976), 369--379) made simplifications to Venkov's argument.

What cases for ${\mathbf Q}(\sqrt{-p})$ are covered by Venkov? When $p \equiv 3 \bmod 4$, the discriminant of ${\mathbf Q}(\sqrt{-p})$ is $-p$. If $p \equiv 3 \bmod 8$ then $-p \equiv 5 \bmod 8$, while if $p \equiv 7 \bmod 8$ then $-p \equiv 1 \bmod 8$, so Venkov had non-analytically proved the formula when $p \equiv 3 \bmod 8$. The case $p \equiv 7 \bmod 8$ remained open.

In 1978 the whole problem was solved. Davis, in a second paper (Crelle 299/300 (1978), 247--255), handled some but not all cases of imaginary quadratic fields with discriminant $1 \bmod 8$ (corresponding to $p \equiv 7 \bmod 8$ for the fields ${\mathbf Q}(\sqrt{-p})$) by non-analytic methods and in the same year H. L. S. Orde settled everything by non-analytic methods. See his paper "On Dirichlet's class number formula", J. London Math. Soc. 18 (1978), 409--420.

1

First, if $p \equiv 1 \bmod 4$ then this result is clear since -1 is a square mod $p$. So here exactly half the squares mod $p$ lie in the first half of $[1,p-1]$. The real problem is for $p \equiv 3 \bmod 4$, where analytic methods show there are more squares mod $p$ lying in the first half of that interval than in the second half because there is a formula for the class number of ${\mathbf Q}(\sqrt{-p})$ that is 1 or 1/3 times $S - N$, where $S$ is the number of squares mod $p$ in $[1,(p-1)/2]$ and $N$ is the number of nonsquares mod $p$ in $[1,(p-1)/2]$. Class numbers are positive integers, so $S > N$, which means in $[1,(p-1)/2]$ the squares mod $p$ outnumber nonsquares mod $p$. Since there are as many squares as nonsquares mod $p$ on $[1,p-1]$, the square vs. nonsquare bias on the first half of this interval forces there to be more squares mod $p$ on the first half than squares mod $p$ on the second half.

For a proof by analytic methods, see Borevich-Shafarevich's "Number Theory", Theorem 4 on p. 346. It is not true that no non-analytic derivations of this bias are known. For instance, Borevich and Shafarevich say on p. 347 that Venkov gave a non-analytic proof for some cases in 1928 (which came out in German in 1931: see Math Z. Vol. 33, 350--374). I should clarify this point since there is a bad typo in Borevich and Shafarevich here. What Venkov did was give a non-analytic proof of Dirichlet's class number formula for imaginary quadratic fields having discriminant $D \not\equiv 1 \bmod 8$. Here Borevich and Shafarevich unfortunately write $D \equiv 1 \bmod 8$. (It's clear in their book that something is wrong because shortly after saying Venkov treated $D \equiv 1 \bmod 8$ by non-analytic methods they say the case $D \equiv 1 \bmod 8$ still awaits a non-analytic proof.) The class number formula only gets an interpretation about squares or nonsquares for the fields ${\mathbf Q}(\sqrt{-p})$, but Venkov was working on non-analytic proofs of the class number formula for imaginary quadratic fields without having this restrictive case as the only one in mind. R. W. Davis (Crelle 286/287 (1976), 369--379) made simplifications to Venkov's argument.

What cases for ${\mathbf Q}(\sqrt{-p})$ are covered by Venkov? When $p \equiv 3 \bmod 4$, the discriminant of ${\mathbf Q}(\sqrt{-p})$ is $-p$. If $p \equiv 3 \bmod 8$ then $-p \equiv 5 \bmod 8$, while if $p \equiv 7 \bmod 8$ then $-p \equiv 1 \bmod 8$, so Venkov had non-analytically proved the formula when $p \equiv 3 \bmod 8$. The case $p \equiv 7 \bmod 8$ remained open.

In 1978 the whole problem was solved. Davis, in a second paper (Crelle 299/300 (1978), 247--255), handled some but not all cases of imaginary quadratic fields with discriminant $1 \bmod 8$ (corresponding to $p \equiv 7 \bmod 8$ for the fields ${\mathbf Q}(\sqrt{-p})$) by non-analytic methods and in the same year H. L. S. Orde settled everything by non-analytic methods. See his paper "On Dirichlet's class number formula", J. London Math. Soc. 18 (1978), 409--420.