There are a lot of mines in the United States. So many that even if Superman correctly guessed that Batman was in a lead mine (as opposed to just a lead-lined room) and in the United States, it would take him a inordinate amount of time to search through them all, even with his super-speed.
Using publicly available information from the CDC, Superman would know that in 2013 (the year that Injustice was first released), there were 349 active metal mines. By going to AbandonedMines.gov, he could find out that there are approximately 6,830 abandoned hardrock mines in Alaska alone, and many more in other US states. Not all of these mines were strictly lead, but some of them were mixed minerals including lead. With many other abandoned mines in other states (e.g. 24,183 in Arizona) there are hundreds of thousands of mines in the United States alone where Batman could be hiding.
And we're just counting ones that were officially registered with the US government; if Batman were hiding in an unauthorized mine, or expanded a mine that was abandoned, then Superman probably wouldn't have any way of knowing that it exists.
Of course, Batman could have also easily been hiding in any of the following places:
- In a lead lined room
- In any mine outside of the United States
- In a place that processes lead (e.g. smelting factory)
Honestly, if Superman were to try checking all of the mines or other places that deal with lead, he would die of boredom long before he actually found Batman.