I don't remember where specifically the shop that sells them is located, but it's somewhere in the Dark World I believe.
An alternative would be to just buy a regular shield, either in Kakariko Village (Dark World), or in the shop located just south of the waterfalls on the east most section of Death Mountain (also in Dark World), then take it to the Fairy Fountain and throw it in. She will give you another Fire Shield in return. You end up saving a lot of rupees this way too, since the regular shield is only 50 rupees, and the Great Fairy will upgrade it for free. The Fire Shield from the shop costs like 500 rupees.