The Bavli, Y'vamos 103 amud 2, quotes a b'raysa:
[The verse says that, for chalitza, the woman removes] "his shoe". I'd think it must be his own shoe; how do I know it can be anyone's shoe? [The verse also says] "the shoe" [meaning] in any event. If so, what does it mean by "his shoe"? A shoe befitting him: excluding one so large he can't walk in it, excluding one so small it doesn't cover most of his foot, and excluding a m'soliyim sandal that has no heel.
The m'soliyim sandal is named after where it was used, or after the fact that it has no heel. In any event, how does the word "his" exclude a m'soliyim sandal? What is less his about such a sandal than about any other sandal or shoe?