I did the unthinkable, and started to read the manual for the product you linked, and in the troubleshooting section there is a theme:
Try another wall socket and make sure all powerline devices are on the same electrical circuit.
If you search the PDF for "circuit" you find this phrase several times. I didn't find where the manual lists using the same phase or circuit as a hard requirement, but you can infer from the troubleshooting that they fully expect you to use the same circuit, which I think is a "dumbed down" way of saying it should be the same phase/leg.
I also found this in their FAQ section:
Q3.5: Can Powerline adapters work if they are separated by different electric circuits?
A: No. If they can pair in the same room, but the powerline LED turns off when you move one powerline device to another area, this usually means they are plugged into separate electrical circuits, preventing them from communicating. Please try different locations.
I think they are being a little concervative, because I do have powerline adapters on different breakers, and they work reliably.
Netgear is more optimistic, which muddies the waters a bit because most of these devices are based on the same protocols and theorys:
Can powerline be used in homes across multiple phases?
Yes, but you will either suffer a noticeable loss in performance, or if the signal is too low the units will not be able to communicate.
Finally the Homeplug (standard the devices use) wiki page states:
One of the greatest technical challenges was finding a way to reduce sensitivity to the electrical noise present on power lines. HomePlug solved this problem by increasing the communication carrier frequencies so that the signal is conveyed by the neutral conductor, which is common to all phases.
In conclusion, the answer appears to be a big "Maybe".