Владивосток был одним из самых оживленных городов Тихого океана, но помимо преимуществ это создавало и проблемы. Здесь каждый год возникали эпидемии, которые привозили с собой выходцы из Китая, Кореи и Японии. В 1886 и 1890 гг. во Владивостоке свирепствовала холера, унесшая много жизней. Михаилу Кузьмичу приходилось тратить много сил на поддержание надлежащего санитарного состояния города. В те времена он был разделен на 24 участка, за которыми на общественных началах наблюдали специальные надзиратели.
Вот строчки из отчета Владивостокской думы за 1895 г.: «Первые сообщения о появлении за границей холеры получены здесь в конце марта месяца. После чего немедленно была созвана особая санитарно-исполнительная комиссия, под председательством городского головы и состоящая из членов: полицмейстера, городового и городского врачей, ветеринарного врача, аптекаря, членов управы с городским архитектором и представителей ведомств: духовного, морского (врач), военного и железнодорожного (врач). Задачей этой комиссии было указать меры к предупреждению появления эпидемии, а равно и меры к борьбе с нею в случае появления. Комиссия обратила первое внимание на количество дезинфекционных средств, на усиление надзора за проходящими судами, на устройство и снабжение всем необходимым помещений для холерных больных и приведение в возможно наилучшее санитарное состояние дворов обывателей города, затем признала необходимым просить о командировании в распоряжение города 3 врачей. Все это и было исполнено городом, о командировании же 2 врачей сделано представление. 20 июля [1895] было получено уведомление, что в Чифу холера приняла эпидемический характер, а 28 июля оказался в городе первый случай заболевания от холеры. С появления эпидемии, согласно мнения той же комиссии были сформированы санитарные отряды с фельдшерами, которые состояли при полицейских участках для поднятия заболевающих и умерших; устроено на берегу три барака (шалаша) у Саперной казармы, Штабной пристани и вблизи дома Конторы госпиталя, в каждом бараке был фельдшер и по 2 человека прислуги и необходимые вещи, как хозяйственные, так и специально относящиеся к поданию первой помощи больному. Кроме сего в распоряжение города были командированы на время эпидемии три врача. Кроме мер, принятых городом, был еще устроен особый карантин с холерными бараками в бухте Диамид, который состоял в исключительном ведении администрации».
Городской голова Федоров бесстрашно нес свои обязанности во время эпидемии: он заходил в холерные бараки, проверял санитарное состояние самых злачных мест города, заглядывал в трюмы судов, приходивших в порт Владивосток. Благодаря его усилиям, а также работе добровольных помощников, эпидемия закончилась 17 сентября 1895 г.