Exploiting the fact that

2*l^2 - 1 == 0 (mod p)

is easy to solve when p == 7 (mod 8) [one solution is Mod(2,p)^((p-3)/4)], that the multiplicative order of 2 (mod p) is automatically odd in this case, and that I had primelimit set above 64000000, I did a quick check on the distribution of the least value of l in comparison to p/2.

The script

? j=0;v=vector(100);forprime(p=7,64000000,r=p%8;if(r==7,j++;l=lift(Mod(2,p)^((p-3)/4));if(l+l>p,l=p-l);f=2.*l/p;m=floor(100*f);v[m+1]=v[m+1]+1));print(j)

found j = 946648 primes p == 7 (mod 8). For each, l is the value < p/2 for which p divides 2*l^2 - 1. In the vector v, v[i] is the number of p for which

(i-1)/100 < 2*l/p < i/100.

[9471, 9426, 9368, 9426, 9499, 9452, 9339, 9539, 9562, 9419, 9612, 9498, 9416, 9576, 9495, 9442, 9453, 9403, 9401, 9484, 9339, 9348, 9367, 9511, 9509, 9424, 9520, 9547, 9605, 9594, 9419, 9627, 9463, 9482, 9474, 9440, 9323, 9530, 9543, 9454, 9497, 9552, 9397, 9306, 9427, 9406, 9558, 9463, 9466, 9520, 9345, 9435, 9338, 9454, 9389, 9396, 9442, 9495, 9461, 9500, 9539, 9593, 9549, 9567, 9399, 9375, 9454, 9600, 9425, 9473, 9463, 9472, 9425, 9430, 9456, 9406, 9601, 9587, 9442, 9628, 9382, 9543, 9487, 9328, 9603, 9524, 9436, 9547, 9475, 9441, 9461, 9456, 9448, 9414, 9443, 9410, 9403, 9501, 9379, 9436]

I'm no expert at statistics, but the distribution looks reasonably close to uniform.

I cheerfully admit that I didn't look at primes congruent to 1 (mod 8). I didn't see any faster way to solve the congruence than using factormod(). Also, I didn't want to bother checking whether the multiplicative order of 2 (mod p) was odd. But I have no reason to expect anything other than uniform distribution in this case either.

If q is a divisor of (the primitive part of) 2^n - 1, n odd, then q = 2*n*k + 1, so k < q/(2*n). Assuming uniform distribution of l-values in (0,q/2) one could say that there's a 1 in n chance that

f(x) = 2*x^2 - 1

will find the factor q before trial factorization. As n increases, the chances decrease, with no positive lower bound.