You can buy them at the end of the jungle stage; instead of going up to the lair, go down and the store there will have potions.

Also, there's a hidden shop in town that has lightning spells and potions; it's located in the air, in a mid-air door that's right below a normally visible door.

There's also a few places to find potions, which respawn whenever you save and quit. I believe there's one beneath the desert, for example; just fall into a pit (you will likely get hit by the enemy here), then swim to the left and (IIRC) there should be a potion there.

(You *do* have the legendary armor and shield, right?)

Armor yes, shield, not sure.

But gosh darn does this seem annoying to do. :(