I'm not sure if I understand completely the usage of the genitive case here, or if this is simply a one-time thing based on this individual expression. If, for instance, Много + кошка = Много кошек and Много + сок = Много сокa, how come the expression 'many times' constructed with Много + раз ≠ много разов, but instead (seemingly) stays in the nominative case? (много раз)
In Russian, some second declension nouns have zero ending in the plural genitive.
These are almost all neuter nouns: лицо/лиц, село/сёл, as well as some masculine nouns: чулок/чулок, солдат/солдат, армянин/армян etc.
Раз is one such word. The plural genitive form of раз is раз.
In Old Russian, all the nouns with the historical stem in -o (this is the majority of masculine and neuter nouns in Russian) had the ending -ъ in the plural genitive, the precursor to the modern zero ending. They had the same ending also in the nominative singular: вълкъ/вълкъ, градъ/градъ etc.
A handful of nouns with the historical stem in -u (like сын, лёд, верх and some others) had the ending -ове in plural nominative and -овъ in the genitive plural. It used to be сынъ (sg. nom) / сынове (pl. nom.) / сыновъ (pl. gen.), домъ / домове / домовъ etc.
Then a kind of exchange took place.
Most (although not all) masculine nouns with the historical stem in -o accepted the -ов paradigm in the genitive plural: волк/волки/волков, город/города/городов, and some even in the nominative plural: кум/кумовья/кумовьёв, хозяин/хозяева/хозяев.
At the same time, most nouns with the historical stem in -u have lost the ending -ов in the nominative plural: дом/дома, верх/верхи etc.
Nouns that have retained the zero ending in the genitive plural are mostly military ranks and specialties (солдат, гусар, драгун, партизан); units of measure (ватт, ампер, вольт, грамм); nationalities and ethnicities (татарин/татар, армянин/армян, грузин/грузин); articles of clothing, especially those that come in pairs (сапог, чулок, валенок); and some other disparate nouns.
This continues to be an ongoing process to this date. As recently as 200 years ago, зуб, пуд, рог had the zero ending in the genitive plural, and the jury's still out on some fruit and vegetable names: помидор(ов), банан(ов), апельсин(ов) etc.
All your examples follow the same rule: много is used with the genitive. But the correct form of genitive of разы is раз, not разов.
Have a look at the declension: https://ru.wiktionary.org/wiki/%D1%80%D0%B0%D0%B7.
For some masculine nouns, the genitive plural is the same as the nominative singular. Notable examples include: раз, глаз, челове́к, солда́т, боти́нок, чуло́к, во́ло́с...
Thus you say пять раз, мно́го раз, па́ра глаз, сто челове́к, ро́та солда́т, копна́ воло́с...
This last one (во́ло́с) is a bit tricky:
- Nom. sing. is во́лос (a single hair)
- Gen. plur. is воло́с (as in копна́ воло́с 'a haystack of hair' - think Boris Johnson)
Here is a more comprehensive list of such words (ignore the words ending in vowels).