Presumably from mule + shoe (“type of horseshoe”). It was named after Muleshoe Ranch, where a mule shoe was apparently found.
Muleshoe