Does the slowdown occur when entering/exiting the city screen, closing/opening dialogs, etc?
I solved that problem on Linux by changing to
output=overlay
or
output=surface
in the config file.
A Windows user solved it by changing to
output=ddraw
instead.
I haven’t tried Master of Magic on Magic DOSBox yet.