By the time stalemate came into being, mate was already a separate word and had lost its earlier Arabic meaning, instead coming to mean "situation from which there can be no escape". In checkmate this meant one player's king couldn't be made safe, and in stalemate that there could be no outcome one way or the other.
I completely made this post up, I have no idea.