In order to battle Mewtwo, you first need to get all 10 trophies in the Stadium Mode as well as the Gym Leader Castle.
Once you have done that, the VS Mewtwo bonus tournament will open up on the map. To access it, simply move your Magne-cursor up to the top. Unlike the other battles in the Stadium and Gym cups, the VS Mewtwo tournament allows you to enter six Pokémon.
Mewtwo knows Psychic, Blizzard, Thunderbolt, and Rest, three damaging moves and one recovery move. Bring along Bug, or Ghost Types to get the advantage. Or you can use a Ditto to transform into Mewtwo and then battle.
In Round 2, it no longer knows Thunderbolt. Instead, it has Amnesia. The best strategy, when using rentals, is to bring a paralyzer that can resist one of Mewtwo's Psychic (like Clefable), and other 5 that know one-hit KO moves (fissure, horn drill, guillotine), more like Nidoking, Seaking, Kingler, Omastar etc. Paralyze it, and do not deal any damage, otherwise it will use rest, and your pokes will be slower than Mewtwo, being not able to get hit by OHKO moves. After paralyzing, just send any of the others, and try to take it down with those moves. One of them will hit it, if they don't, just retry.
If you're using Pokémon from your Game Boy, just bring a Snorlax with selfdestruct.