You don't need to find all of the fish. I think it's just whatever number is in the base game. 20 or 21 will do it.
I usually add the Riverview fish nursery to my games, and add spawners for fish from the WA worlds. I actually try to add 2 of the RV nurseries, one for saltwater fish and the other for freshwater fish. Depends on the world I'm playing and what fish spawners are available. I don't think of it as cheating. I don't think that wish was meant to require travel.
edit: some of the EP fish can be caught by fishing in open water (that is, not at a fishing spawner spot). Kissing Gourami for example, and maybe the Sea Sludge.