Actually, stay on that one spot and start using the good rod/super rod. I found mine using the Super Rod... Once you run into him and you keep fishing in that same spot, you'll run into him all the time BECAUSE his encounter rate increases by a lot, making Magicarp less common than Feebas! That's ONLY if you stay on that one square; move and you could ruin it.
But if you land on the right square, he's commonly found right away.
Like I said, I had experience. And in this game, too.
Avatar: In memory of ieatwyverns <3
Thank you, Vasco <3