Таких театров повсюду – пруд пруди.
I'm at least aware that a quantity of something is expressed with the genitive case in Russian, but I'm not sure what necessitates the use of genitive in this case. Is it due to "пруд пруди" or "повсюду"?
The dash in that expression is a substitute for the omitted words ... так много (or столько), что хоть... So the genitive here comes from the combination "театров много (столько)".
Таких театров повсюду столько, что хоть пруд пруди.
The expression пруд пруди is just attached, without any influence from it on that case. It literally refers to a technology of creating a pond by making a dam of some otherwise useless material which is galore (theatres here). The expression is used to emphasize an excessive quantity/number of something and literally means 'even enough for ponding a pond'.
The source I gave in the other answer also answers this. The expression used to feature the instrumental case — пруд пруди (чем?) — because that’s what makes sense taken literally, but with the original meaning fading and the expression becoming just a synonym of “много (чего?)” the grammar followed suit.
This is just one of many examples of Fenno-Ugric substratum in Russian. Russian Genitive here actually conveys the meaning of Partitive (marked explicitly in phrases like надо бы чаю instead of чая only) and follows the same logic as it is the case in most of modern Fenno-Baltic languages.
Here, it stands for indefinite plural (uncountable plural), cf. Finnish
Sellaisia teattereita löytyy kaikkialta paljolti.
In Finnish, the case is a Partitive Plural marking the uncountable abundance.