  We establish cutoff for a natural random walk (RW) on the set of perfect
matchings (PMs). An $n$-PM is a pairing of $2n$ objects. The $k$-PM RW selects
$k$ pairs uniformly at random, disassociates the corresponding $2k$ objects,
then chooses a new pairing on these $2k$ objects uniformly at random. The
equilibrium distribution is uniform over the set of all $n$-PM.
  We establish cutoff for the $k$-PM RW whenever $2 \le k \ll n$. If $k \gg 1$,
then the mixing time is $\tfrac nk \log n$ to leading order. The case $k = 2$
was established by Diaconis and Holmes (2002) by relating the $2$-PM RW to the
random transpositions card shuffle and also by Ceccherini-Silberstein,
Scarabotti and Tolli (2007, 2008) using representation theory. We are the first
to handle $k > 2$. Our argument builds on previous work of Berestycki, Schramm,
\c{S}eng\"ul and Zeitouni (2005, 2011, 2019) regarding conjugacy-invariant RWs
on the permutation group.
