The best spot to catch these is in Yhoator Jungle in the pool in front of the Temple of Uggalepih using a fly lure. If you fish in the pool on the East side of the entrance, every single ! that isn't a rusty item will be Elshimo Frog.
Yhoator Jungle (J-11) directly next to Ugly Poo temple where you'll see a pretty waterfall. Use a fly lure and wait for ! good feelings. May catch Elshimo newts as well.
