Multiplication mod 2 without extra registers
Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.