Magnetic forces do not perform work because they are always perpendicular to the motion of the charged particle they act on. However, it is possible to transform the energy stored in a magnetic field into the bulk motion of a conductor carrying a current. I'll give one heuristic.
Consider two long wires running parallel. Give them currents running in the same direction, and hold the wires still for a time that's long compared to the distance between them divided by the speed of light.
Now there is a magnetic field from the first wire at the location of the second and vice versa. The wires attract each other. Once released, they experience an acceleration towards each other.
However, this analysis only holds up until the first moment the wires are released. After that, they are moving towards each other. This motion of the wires entails a motion of the charge they carry - a current. We will need to account for this current.
Say the wires run horizontally on your computer monitor, and the current is to the right. Then the top wire is pulled down, and its current is now mostly to the right and a little bit down. The magnetic field it feels is pointing towards you, out of the monitor. Thus, the force on this top wire points mostly down, but it also points a little bit backwards.
Similarly, the force on the bottom wire is mostly up, but also a little bit backwards. The backwards components of the magnetic forces act to decrease the currents in the wires. If the currents in the wire decrease, the magnetic field gets weaker. In this way energy from the magnetic fields gets converted into the bulk motion of the wires carrying the currents.
The magnetic forces did not actually do any of the work here, though. In the absence of any wire, the charged particles in the magnetic field would like to move in circles. Instead, electrical forces between the particles and the wire they're trapped in forced the particles to stay inside the wire instead. These electrical interactions between the charged particles and the rest of the wire did the work that accelerated the wires towards each other.
Also, it is obvious that the work done is due to force of "magnetic field" on "moving electrons".
This part is problematic, as you probably already know (you've put the quotes). There is macroscopic magnetic force on wire 1 due to wire 2 given by $\int \mathbf j_1 \times \mathbf B_2 \,d^3\mathbf x$. Often this force is present but balanced by other forces so the wire does not move and there is no work involved.
When wire moves and kinetic energy increases, work is done on the wire. However this work is not due to the above force, since it is everywhere perpendicular to the motion of the charges it acts on, as you wrote above.
The only force that can do work on the wire and increase its kinetic energy is electric force. Since there are no external electric fields, it can be only the electric field of the wire 1 itself. This is always present, since there is current inside the wire, but usually does not move the wire in a noticeable way since mechanical equilibrium is easily established in common circuits. When the electric and magnetic forces cease to be counteracted by contact and mechanical forces (say, attached wire gets loose), the wire 1 will have non-zero acceleration due to magnetic force of wire 2, the power of this force being always zero. However, as soon as the wire 1 accelerates, this produces change in its own electric field. The changed electric field will now work on the wire itself and give it kinetic energy. This will happen at expense of the energy of magnetic field of the wires (and the source maintaining the current).
EDIT
The above explanation does not seem correct to me now, because one can extract work from the system of current carrying conductors very slowly, in which case the induced electric field will be negligible, while the force doing work is still great and given by the formula like $\int \mathbf j_1 \times \mathbf B_2\,d^3\mathbf x$. Please remove the green sign of acceptance. The real answer to your question requires more insight.
Best Answer
First, just as a reminder, the force of a particle due to a magnetic field is $$\vec{F_B}=q\vec{v}\times\vec{B}$$. As you mentioned the force due to the magnetic field is always perpendicular to the velocity but it is also perpendicular to the magnetic field so the differential work is $$dw_B=\vec{F_B}\cdot d\vec{s}=q(\vec{v}\times\vec{B})\cdot \vec{v}dt=0 $$ so we have verified that the work is indeed zero due to the magnetic field. $\vec{F_B}$ cannot change the speed of the particle so it cannot change it's kinetic energy, but it can change the direction of $\vec{v}$. The total force on the particle is $$\vec{F}=q(\vec{E}+\vec{v}\times\vec{B})$$ so the total work on a particle is $$dw=q\vec{E}\cdot\vec{v}dt$$ which is non zero.
Now lets consider the wire which is really just a group of moving charges. positive particles inside the wire are pushed upward in the wire due to the magnetic force and negative particles are pushed downward (where the up-down directions are orthogonal to the wire velocity v and magnetic field B). The separation of charges induces an E field which produces a force on the respective particles in the opposite direction. In equilibrium the two forces balance and we have $$qvB=qE$$ and the emf across length l is $$\mathcal{E}=El=Bvl$$. When you are talking about an EMF in the wire you should consider the wire in a magnetic field closed by a loop outside the field (see http://hyperphysics.phy-astr.gsu.edu/hbase/electric/elevol.html#c4 , In your problem the circuit is not closed so the wire goes nowhere) The induced emf can be seen as the work done per unit charge so it is really the E field that changes the velocity of the particles (changes their kinetic energy)perpendicular to the B field.