The Polish name Mikołaj is held to correspond to the Nicholas family of given names, as evidenced by the Russified name of Mikołaj Kruszewski.
As this is an odd sound change, my question is why? My first guess would be interference from Michał and other variants of Michael.
You are absolutely right, the change N > M is due to the influence of Michael.
That happened not only in Polish, but also in
Микола, Миколай (Mykola, Mykolaj)Мікалай (Mikalaj)MikulášMikławšMiklawšMiklavž.UPD: Best wishes on Saint Nicholas' Day, which is celebrated today by most of the Eastern Orthodox!
