XVIII. f. synon. [obsolete] stale (XV-XVII), prob. - AN. estale, position, f. estaler be placed, f. Germ. *stall-; see STALL1, MATE2.
STALL1 is "division in stable or shed", from Old English steall from Proto-Germanic *stallaz, which the ODEE traces to *sta- "stand" (i.e. PIE *steh₂). On the other hand, the AHD traces it to PIE *stel- "to put, stand", an unrelated root.
The Middle English verb was stālen "in chess: to trap (an opponent's king) in stalemate", and the noun was stāle "A stalemate in chess". It's also related to finger-stall, a sheath worn over the finger for protection. zmjezhd has a collection of Google Books scans of finger-stalls.