they won't appear over water, i'm pretty sure. here's a tip, get a pokemon level 45 or so with one of the non-escaping moves. buy bunches of max repels and fly to vermillion. go onto the route to the north and stand next to the grass, use a repel and RUN through the grass. continue doing so until the legendary dog appears. i suggest inflicting it with a status condition first, unless you are willing to use your master ball on it.
I can't imagine Entei on a water route, but hey whatever XD
What I do is get super repels and a Pokemon around 35-40 to lead and go to the patch of grass below Pewter City and run around there. If I don't find it by the time my super repel wears off, I fly (Keyword: FLY) back to Pewter city and repeat.
Okay you need something with a move to keep it from escaping and something guaranteed to weaken them without fainting them and all that stuff first.
You need to of seen it in your Pokedex, if you haven't then it makes it harder but still possible.
I think the best place for me was right of Fuchsia City.
The thing with Suicine, Entei, and Raikou is that everytime that you change routes or citys/towns it changes too so flying won't help because it basically flys too. It WILL NOT change routes unless you either see it and it runs from you or you changes routes (very imporant). Also I'm about 90% certain that it will always be the first Pokemon you see on the route if it is on that route (why it'll work without the Pokedex info).
Make sure the Pokemon with the nonescaping attack has high enough speed to get first attack and is first in your party (I used Golbat from Cereulian Cave).
Go over to the little building dividing Fuschia from the Route to the right of Fucshia. If you have the Pokedex info on it then check the Pokedex and see if it is on that route. If not go into the building and then back onto the route and check again. It will eventually be on the route.
If you don't have the info then just run into the grass and hit a few Pokemon if it's not the Cat(Dog) the just run away and run around if it doesn't show up soon go back into the little building then back onto the route.
I spent like hours and hours figuring out how this works. So let me know if it helps.
The dogs do appear on water and if ure looking 4 ure legedary dog i say look at route 1 in grass just under vermillion thats where i found my good buddy Suicune
;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245; ;245;
Try transfering entei from a pokemon colleseum game to your game if you have it or anybody else has it. Transfer it back. The data will be recorded in your pokedex as well as entei's location. That will make it easier to track down. I prefer doing it this way because it makes catching entei a breeze.