Every permutation is a product of two permutations of order 2

I think you are working in the right direction. Essentially, you build upon the following formulas (note that I compose permutations left-to-right)

$$ (12) \cdot (23) = (132) $$

$$ (12)(34) \cdot (23) = (1342) $$

$$ (12)(34) \cdot (23) (45) = (13542) $$

$$ (12)(34) \dots \cdot (23) (45) \dots = (135 \dots 6 4 2). $$

As an example of decomposing a cycle into two sets of transpositions:

An explicit decomposition of the cycle $(12...n)$ is also given by the product of $r(12)r(34...n)$ and $r(123)r(4...n)$ where $r$ means order reversal, i.e. $r(123)$ maps $123$ to $321$. Clearly each factor is of order 2.