Distribute to pairs with efficient algorithms
Yes, that works, but I would skip making/faking Eulerian cycles and just execute your idea directly:


If the list is empty, you're done. Otherwise, choose an arbitrary $(a, b)$ from your list, output it and remove it.
Find the unique $(c, b)$ in your list, output it and remove it.
If $(c, d)$ exists in the list, output it and remove it. Otherwise go to 1.
Find the unique $(e, d)$, output it, remove it, let $c \leftarrow e$ and go to 3.