So I tried to upgrade it. The first time I did this (on RouterOS 7.12.1) it downloaded the firmware, showed "Preparing to update", then "Updating" and a percentage value that slowly progressed. However when it finished and the modem started up, it still had the 16M16 version. On further attempts, it downloads the firmware, but after "Preparing to update" it just quits and starts up the modem.
Then I upgraded RouterOS and firmware on RB5009 to 7.13. After that the LTE interface also shows a message that "A newer version of modem firmware is available!". There is still the same problem with updating it as on 7.12.1.
Then I looked at the modem firmware upgrading instructions and noticed that it says this:
Before attempting LTE modem firmware upgrade - upgrade RouterOS version to latest releases How To Upgrade RouterOS
So did I mess something up? How do I fix this? The modem still works correctly, the only issue is that I can't upgrade its firmware.