The Russian language does not have the letter "H" (and most Russians have trouble pronouncing the letter H), so, generally, the letter "H" is replaced by "G". In some exceptional cases (in certain words or names), the letter "H" is just removed instead.
Hence, Mohamed because Magomed. The first "o" is replaced by an "a", because, in Russian, the first "o" in a word is pronounced as an "a". So they decided to write it as they would say it.
Basically, Russians also pronounce the name as Magomed, not Mohamed. Languages from the Caucasus (such as Avar) do have the letter H and someone like Khabib has no problem pronouncing his name as "Nurmohamed".