Suppose we hold two bar magnets with opposite poles facing each other a certain distance away. We let go and the magnets fly towards each other. We observe that the magnets gain kinetic energy. Then work must have been done on their masses.
I'm afraid not. You do work when you pull the magnets apart. That's when you add energy to the system. When you let go and they move towards one another, electromagnetic potential energy is converted into kinetic energy, which you can extract and use, but no new energy is added to the system.
I am told that magnetic forces are always perpendicular to the velocity vector and hence cannot do work. But clearly here, the magnetic field has done work.
It hasn't, not really. Yes we have a force and a distance, but there's no added energy.
How can we reconcile the motion of the bar magnets with the statement about magnetic forces. I simply don't get it. If the magnetic field isn't what's providing the accelerative force, then what is?
The interaction between electromagnetic fields, or more simply, the magnetic fields, do accelerate the magnets towards each other. Just like the Earth's gravitational field accelerates a brick. But you do work on the brick when you lift it, that's when the energy is added to the system, not when the brick falls down. Gravity merely converts potential energy into kinetic energy. When this is dissipated, you're left with a mass deficit, see Wikipedia. It's similar for the electron and proton, and for a pair of magnets.