По имени крымского Мариамполя, что означает «город матери Марии». В честь императри­цы Марии Федоровны. Еще есть Марианополь и версия, популярная в народе "море у поля" )) ну а достоверных сведений насчет переименования Павловска в Мариуполь нет, насколько я знаю.