I catch female Munchlax all the time. Whenever I encounter a shaking tree I save my game, then find out what Pokemon is in said tree. If it's a Munchlax I proceed to soft-reset and go to my PC box and retrieve my male Clefairy with cute charm, (Nicknamed Casanova) put him at the front of my team, return to the tree and press A.
Leftovers has a 5 to 50% chance of being held by wild Munchlax.
The ability Cute Charm increases the odds of encountering Pokemon of the opposite gender by 66.6%, regardless of gender ratios.