Misr is not a native name but a purely Arabic one, given after the conquest.
There is not a general rule. Arabs used geographical names (Maghrib) descriptive names in Arabic (Sudan, from Bilad al-Sudan, "Land of the Blacks") and, more often, roughly transliterated local names like Fars, Ifriqiyya, Andalus, Siqilliya.
The most likely ideas I have are al-Bilad al-(something) (the land of ... ) or al-Maghrib (something (the ... West) which are both somewhat descriptive.
If the discoverer goes there to reach the "Indies" (unlikely) something like "China of the West" is possible (it would Sin Gharbi, I think, or Sin al-Gharb).
Al-Bilad al-jadid would mean "new land/country" and is quite possible too.
"ba'd al-Bahr" or "ba'd al-Muhit" are my ideas for "beyond the Ocean". It would begin as a descriptive phrase after noun such as "ard" or "bilad" or pronouns like "ma" ("ma ba'd al-Muhit" would mean "what's beyond the Ocean" more or less) but after a time would be used alone probably.
e bravo Falecius. Colto, analitico e inventivo.