They most certainly do as a Pokemon's nature is determined the moment it is encountered. Natures also boost respective stats, barring (Bashful, Hardy, Serious...Natures).
As you might already know, Modest boost the Special Attack stat but lowers the attack stat,
Since Mewtwo already has an extremely high special attack, it's special moves will be doing some serious amount of damage. Psychic is a special move so it is most definitely normal that it did a huge amount of damage. Not to forget that it is a STAB move
However if Mewtwo was to use Earthquake with that Nature, it will be doing much less damage then an Adamant Natured Mewtwo. However IVs play a role in this too but a Modest Natured Mewtwo would be doing some serious damage anyways