So white obviously has to start with
1.Kxe1 because otherwise the black knight escapes. Now black can only play Qa2-a1-a2, and white can't move the king anymore or black will immediately break out.
Then,
We want to promote to a knight and give checkmate. If the rook on b3 were undefended, we can do it from there. (d3 will always be defended by the rook).
So we remove the defending pawn(s), and have to play Nxb3# when the queen is on a1. Since the knight always moves to squares of alternating color, and so does the pawn after the first move, and so does the queen in this situation, all we need to do is to move it to a square of the opposite color of the queen on its first move, and it will work out.
But the order we take the pawns is important! If we take c4 first, then black can later choose to either play c5-c4 or omit it, thereby causing our knight to be on the wrong color square at the wrong time. So first c5, then c4, then b3.
So
[FEN "8/8/8/2p5/1pp5/brpp4/qpprpK1P/1nkbn3 w - - 0 1"]
1. Kxe1 Qa1 2. h3 {Queen is on black, so the pawn goes to white! Now we keep it that way} Qa2 3. h4 Qa1 4. h5 Qa2 5. h6 Qa1 6. h7 Qa2 7. h8=N Qa1 8. Ng6 Qa2 9. Ne5 Qa1 10. Nd7 Qa2 11. Nxc5 Qa1 12. Na4 Qa2 13. Nb6 Qa1 14. Nxc4 Qa2 15. Na5 Qa1 16. Nxb3#
(moves stolen from Glorfindel as he was slightly faster, but the reasoning is mine ;-))