Are you using the correct fishing rod?
if you want, this is a list of all the poliwag locations.
Poliwags can be found in the following places: Route 6, 22, 28, 30, 31, 35, 43, 44, 45, Blackthorn City, Cerulean Cave, Cliff's Edge Gate, Ecruteak City, Ilex Forest, Mt. Moon, Mt. Silver, Ruins of Alph, Violet City, Viridian City