Let both particles have amplitude $A$. Let $x_1 = A\sin(\omega t)$, and $x_2 = A\sin(\omega t + \phi)$. At the instant of crossing, $x = \frac{A}{\sqrt{2}}$.
Then, $\sin(\omega t) = \frac{1}{\sqrt{2}} \Rightarrow \omega t = \frac{\pi}{4}$; thus, $x_2 = A\sin(\frac{\pi}{4} + \phi) = \frac{A}{\sqrt{2}}$.
Also, they are moving in opposite directions $\Rightarrow$ velocities are opposite: $\cos(\omega t + \phi) = -\cos(\omega t) = -\frac{1}{\sqrt{2}}$.
So, $\sin(\frac{\pi}{4} + \phi) = \frac{1}{\sqrt{2}}, \cos(\frac{\pi}{4} + \phi) = -\frac{1}{\sqrt{2}} \Rightarrow \frac{\pi}{4} + \phi = \frac{3\pi}{4} \Rightarrow \phi = \frac{\pi}{2}$.
Thus, the phase difference is $90^\circ$.