Easier (for me, at least) than two magnets is two parallel current-carrying wires attracting each other. The force of attraction is equal to the component at right angles to the wire of the magnetic Lorentz force on the charge carriers – the so-called Laplace force.
As soon as the wires start to move together (and work is done on them) the charge carriers' velocity acquires a component at right angles to the wire, and the magnetic Lorentz force acquires a component along the wire. So if the charge carriers are to keep moving at the same speed, work has to be done on them by the electric field set up by the battery; in other words a back-emf has to be overcome.
So it's the battery that ultimately supplies the work done on the wires as they move together. The magnetic Lorentz force acts a bit like a pulley, changing the direction of the force that does work.
I imagine that the case of two magnets attracting can be analysed in a similar sort of way. But then I do have a vivid imagination...