When you get to sootopolis (The Last Gym) inside the city you will see a lake surf in the lake Untill you see a dark patch of water.
Relicanth can be located in Underwater Routes 124 & 126.
For you to access those route's you must have a Pokemon with surf/dive.
The reason your unable to catch one is because they have a 5% catch rate.
I love Weird things ¯(°_o)/¯