The Evil Cipher Mayor isn't the "Final Battle" of Colosseum. The last battle
is with a guy called the "Deep King" (I believe that's what his name was)
in the Deep Colosseum (use D-Disk from Snagem Hideout on the UFO in
"The Under" to get there). I think I remember him having six pokemon
around Lv.69.
In any case, I had some problems with the Mayor too. I beat him the 2nd
time around.
My Espeon was completely useless against both his Tyranitar (which I
somehow managed to capture using just 1 Ultra Ball and not inflicting any
status problems on his pokemon - seems kind of odd for "the toughest
shadow pokemon in the whole game" [which you're supposed to use the Master Ball on] was captured by me without utilizing it) and his Aggron. I
still have my Master Ball, even though I have beaten the whole game and
have nothing else to use it on.
I believe that in my party, I had Entei, Suicine, Raikou, Espeon, Umbreon
and Tropius. Seemed to work well for me. I suggest one of the fast fire
types to battle Aggron, such as Typhlosion or Entei.
Hope you're successful in beating him this time around!