Surf on the lake in sootopolis, then dive down in it. You can only get Relicanth in the grass Underwater in Route 124 and 126. It's only 5% chance to find it.
Now like any Pokemon, try putting it to sleep. It won't take much to catch it asleep.
Hope I helped! :)