So Gardevoir can have Trace, but which would activate first Mummy or Trace, and if the one that goes first activates, will the second ability fail?
No, trace can copy the ability mummy, so when the battle starts Gardevoir will trace the mummy. They do not have to touch each other to get the same ability.
Source for this is here
