Well this is the genuine move set you'd expect to find on a Mega Gyarados:
252 Atk, 252 Spd, 4 HP, with Waterfall, Dragon Dance, Earthquake, and either Ice Fang or Stone Edge as it's moves.
Considering this there are a few notable Pokémon I'd recommend as good counters to Mega Gyarados.
First up:
Conkeldurr
Conkeldurr's genuine move set is 252 Atk, 252 HP, 4 Sp.Def, with Knock Off, Ice Punch, Mach Punch and Drain Punch as it's moves, and the Assault Vest as it's held item. Here are a few calculations of Conkeldurr vs Mega Gyarados, but seriously who would stay in with Mega Gyarados against a Conkeldurr this can give you the upper hand if they switch out and you use Knock Off.
Conkeldurr Attacking:
252+ Atk Conkeldurr Drain Punch vs. 4 HP / 0 Def Mega Gyarados: 266-314 (80.1 - 94.5%) -- guaranteed 2HKO
252+ Atk Guts Conkeldurr Drain Punch vs. 4 HP / 0 Def Mega Gyarados: 396-468 (119.2 - 140.9%) -- guaranteed OHKO
Gyarados Attacking:
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 171-202 (41.3 - 48.7%) -- guaranteed 3HKO
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 171-202 (41.3 - 48.7%) -- 12.5% chance to 2HKO after Stealth Rock
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 171-202 (41.3 - 48.7%) -- guaranteed 2HKO after Stealth Rock and 3 layers of Spikes
+1 252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 256-303 (61.8 - 73.1%) -- guaranteed 2HKO
+2 252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 342-403 (82.6 - 97.3%) -- guaranteed 2HKO
+2 252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Conkeldurr: 342-403 (82.6 - 97.3%) -- 25% chance to OHKO after Stealth Rock
Secondly to the playing field:
Mega Venusaur
Many people give Mega Venusaur different move sets but never the less it pretty much always has Sleep Powder and Giga Drain which can be a real problem for Mega Gyarados. Not to mention Ice Fang is only 1x Super Effective thanks to Thick Fat. Here are a few calculations of Mega Venasaur vs Mega Gyarados, but seriously only an idiot would stay in with Mega Gyarados against Mega Venusaur.
Venusaur Attacking:
4 SpA Mega Venusaur Giga Drain vs. 4 HP / 0 SpD Mega Gyarados: 152-182 (45.7 - 54.8%) -- 62.1% chance to 2HKO
4+ SpA Mega Venusaur Giga Drain vs. 4 HP / 0 SpD Mega Gyarados: 168-200 (50.6 - 60.2%) -- guaranteed 2HKO
252+ SpA Mega Venusaur Giga Drain vs. 4 HP / 0 SpD Mega Gyarados: 206-246 (62 - 74%) -- guaranteed 2HKO
252+ SpA Mega Venusaur Giga Drain vs. 4 HP / 0 SpD Mega Gyarados: 206-246 (62 - 74%) -- guaranteed 2HKO after Stealth Rock
Gyarados Attacking:
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 0 Def Mega Venusaur: 148-176 (40.6 - 48.3%) -- guaranteed 3HKO
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 0 Def Mega Venusaur: 148-176 (40.6 - 48.3%) -- 64.8% chance to 2HKO after Stealth Rock
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 0 Def Mega Venusaur: 148-176 (40.6 - 48.3%) -- guaranteed 2HKO after Stealth Rock and 3 layers of Spikes
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 252+ Def Mega Venusaur: 112-132 (30.7 - 36.2%) -- 54% chance to 3HKO
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 252+ Def Mega Venusaur: 112-132 (30.7 - 36.2%) -- guaranteed 3HKO after Stealth Rock
252+ Atk Mold Breaker Mega Gyarados Ice Fang vs. 252 HP / 252+ Def Mega Venusaur: 112-132 (30.7 - 36.2%) -- 96.9% chance to 2HKO after Stealth Rock and 3 layers of Spikes
Next in line:
Scizor/Mega Scizor:
Scizor's EV Spread is most commonly 252 Atk, 252 HP, 4 Sp.Def. It's moves can vary depending on the player using it but it pretty much always has Bug Bite. If Scizor is not holding the Scizorite it most likely has a Choice Band as it's held item.
Scizor/Mega Scizor Attacking:
252+ Atk Choice Band Technician Scizor Bug Bite vs. 4 HP / 0 Def Mega Gyarados: 450-530 (135.5 - 159.6%) -- guaranteed OHKO
252+ Atk Technician Mega Scizor Bug Bite vs. 4 HP / 0 Def Mega Gyarados: 336-396 (101.2 - 119.2%) -- guaranteed OHKO
Mega Gyarados Attacking:
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Scizor: 163-193 (47.3 - 56.1%) -- 81.6% chance to 2HKO
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Scizor: 163-193 (47.3 - 56.1%) -- guaranteed 2HKO after Stealth Rock
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Mega Scizor: 123-145 (35.7 - 42.1%) -- guaranteed 3HKO
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Mega Scizor: 123-145 (35.7 - 42.1%) -- guaranteed 2HKO after Stealth Rock and 3 layers of Spikes
Who's next you ask?
Mega Heracross
Mega Heracross's move set normally consists of an EV Spread of 252 Atk, 252 HP, 4 Sp.Def, with Pin Missile, Close Combat, Rock Blast and Bullet Seed as it's moves.
Mega Heracross Attacking:
252+ Atk Mega Heracross Pin Missile (5 hits) vs. 4 HP / 0 Def Mega Gyarados: 550-660 (165.6 - 198.7%) -- guaranteed OHKO
Mega Gyarados Attacking:
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Mega Heracross: 145-172 (39.8 - 47.2%) -- guaranteed 3HKO
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Mega Heracross: 145-172 (39.8 - 47.2%) -- 46.5% chance to 2HKO after Stealth Rock
252+ Atk Mold Breaker Mega Gyarados Waterfall vs. 252 HP / 0 Def Mega Heracross: 145-172 (39.8 - 47.2%) -- guaranteed 2HKO after Stealth Rock and 3 layers of Spikes
Surely their can't be more?
Theirs actually a lot more that I haven't mentioned but I'll leave it as that. Fast and powerful Electric types may be able to OHKO Mega Gyarados, Pokémon such as Jolteon with a Choice Specs, Thundurus-T, Mega Manectric, may be even Zapdos. Other Fighting type Pokémon such as Mega Medicham and Machamp would also be ideal, as would other Grass types such as Ferrothorn and Ludicolo.
Source: http://pokemonshowdown.com/damagecalc/
Hope I helped :)
