Edit: This is the best and the fastest version. $n$ is gone now and the guaranteed relative precision is $1/N^2$ (the constant $1$ is correct, so if you want $10^{-3}$ accuracy (to compare with Mathematica time), just set $N=34$ and get $10^6$ pairs in under 10 seconds. The time is essentially proportional to $N$. For $10^{-5}$ accuracy $N=340$ and 83 seconds suffice. I'll explain the algorithm a bit later; now it makes sense :-)
Edit 2: The outline of the algorithm.
We shall use the averaging over the projections. If we take the discrete set of $N$ equally spaced lines $L_j$, then the approximate formula is
$$
|z|\approx \frac{\pi}{2}\frac 1N\sum_{j=1}^N |P_j z|
$$
where $P_j$ is the orthogonal projection operator to the line $L_j$.
The relative accuracy of this approximation can be easily computed and is, as I said, $1\pm N^{-2}$. The computation of the average projection is going to be exact.
For each projection, we need to evaluate the convolution of $A(z)=|z|$ with four normalized characteristic functions $F_j$ of intervals $[-U_j,U_j]$ at some point $x$. We arrange $U_j$ in the increasing order, so that $U_0<U_1<U_2<U_3$ and do the honest convolution of the absolute value with the third and the fourth function, so we have an explicit formula for $A*F_2*F_3$, which is a cubic spline with partition points $\pm U_3\pm U_2$. The convolution $F_0*F_1$ is just a linear spline, which, when shifted to $x$, has the partition points $x\pm U_0\pm U_1$. We thus need to integrate the product of the two splines, which is the fourth degree spline with known partition points. This is done by arranging the partition points in the increasing order and applying the 3-node Gauss quadrature on each partition interval in the support of $F_0*F_1$. That's it.
I tried to implement it in the fastest way possible, so some parts may look a bit strange. The function $gghh()$ is essentially the product of $A*F_3*F_2$ and $F_1*F_0$, the function $F()$ does the integration job over a single partition interval (up to a constant) and $D()$ takes care of setting the projections and determining the partition intervals of interest. However, once the idea of the program is clear, you can certainly try to see if your code writing skills are better than mine :-)