Some tentative thoughts:
Preliminaries
A checkmating move is either a discovered check, or a direct check. (Possibly both, but likely not relevant). Any proposed checkmate move must consider each possible form.
- B,N,R,P: can direct check or discovered check (unless starting in a corner, or moving along an edge in the case of R).
- K: can discovered check
- Q: can direct check
AFAIK, any possible move is a candidate for a checkmate except:
- a K move along the side of the board
- a B move from one corner to the other
There aren't many moves that really force the opposing king to be in a particular spot. Pawn moves that finish on the edge of the board (eg, a3-a4# or b3xa4#) are the only exceptions (in this case, the king must be at b5). Many moves (say Bb2c3#) are more easily reached with a discovered check (say, a rook along the b file or 2nd rank).
Assuming for the moment that White is mating, the number of half moves required can be described as:
- White: (moving mating piece into position) + (getting other pieces out of the way of mating piece) + (capturing pieces to help king) + (moving pieces into position to attack king's escape squares) + 1 (mating move)
- Black: (getting king into position) + (moves capturing pieces to help mating piece) + (moving pieces into king's escape squares)
Possible goals
It's not immediately obvious which of these mutually incompatible goals is most important:
- forcing the king to move to an inconvenient square far away
- forcing the mating piece to do the same
- choosing a mating location that requires a lot of pieces to enclose (such as the centre of the board, rather than on an edge, or next to where other pieces start)
A good way of forcing the black king to move a long way is for the mating move to be a king move from rank 1 to 2 or similar - so the discovered attack is along a rank.
Unpromising avenues of exploration
- Pawn promotions: it only takes 5 moves, and the goal is close to where the mated king starts, where it is already fairly trapped by the edge of the board and its own pieces.
- Queen moves: hard to see how this would ever take longer than a rook or bishop.
Some possible candidate moves (with White mating)
Kb2xb1
I now realise that Black's king could be mated by a bishop on a1, like this:
- e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#
[FEN ""]
1. e4 Nf6 2. Qf3 g6 3. Na3 Bh6 4. b3 Kf8 5. Rb1 Nxe4 6. c4 Nxd2 7. Kd1 Nxb1 8. Kc2 f5 9. Bb2 e5 10. Ba1 e4 11. Kb2 Kg7 12. Qxf5 Qg8 13. Kxb1#
That's 13 moves, and definitely not optimal.
Kb1xb2
By having the king start on the first rank, we ensure the only discovered check is a rook along the same rank, so black's king must cover the whole board.
Along these lines:
rnbq2nr/pppppp1p/8/8/2P1P3/3P4/PbQ3PP/RK2kBNR w KQ - 0 1
This can be achieved in 13 moves (25 half-moves), and likely fewer:
[FEN ""]
1. d3 g6 2. c4 Bh6 3. f4 f6 (3... f5 4. Kd2 Bxf4+ 5. Kc2 Kf7 6. Na3 Kf6 7. Kb1 Kg5 8. Qc2 Bxc1 9. c5 Kf4 10. c6 Ke3 11. cxb7 Kf2 12. e4+ Ke1 13. h4 Bxb2 14. Kxb2#) 4. f5 Kf7 5. fxg6+ Kxg6 6. Na3 Bxc1 7. Qb3 (7. Qc2 Bxb2) 7... Bxb2 8. Kd2 Kg5 9. Kc2 Kf4 10. Kb1 Ke3 11. Qc2 Kf2 12. e4+ Ke1 13. Kxb2#