Here is Eytan's proof in more detail. First, there is a canonical way to write the cycle decomposition of a permutation. You order the cycles in descending order based on the largest member they contain, then you order each individual cycle to start with this largest member. An example of a permutation written in this canonical form is
Given such a permutation in which all cycles have odd length and $n$ is even, there must be an even number of such cycles, so we can pair them up and then have one of the cycles give up a member to one of the other cycles. Let's do this by moving the last member of the second cycle to the end of the first cycle, so for example
$$(614)(523) \to (6143)(52).$$
Note that the result stays in canonical form. The inverse of this transformation is as follows: go through each of the even cycles and compare their last members to the first (biggest) members of the next cycle. If it's bigger, it gets split off into its own odd cycle of length $1$, and the two are paired up as above. If it's smaller, it gets tacked onto the end of the next cycle, and the two are paired up as above.