Gemara

(Beraisa) Suggestion: Perhaps "his shoe" teaches that the Yavam must wear his own shoe!

Rejection: The Torah repeats "shoe" to include another man's shoe.

Question: If so, why does it say "his shoe"?

Answer: This teaches that it must be proper for him. This excludes a shoe too big for him to walk in, or too small and does not cover most of his foot, or an open shoe without a heel.

Yevamos 101a (Mishnah): Chalitzah with a Min'al (a soft leather shoe) is Kosher. If the sandal was not the Yavam's, or it was big but he could walk in it, or was small but covered most of his foot, the Chalitzah is Kosher.

102 a: This connotes that a Min'al is b'Di'eved. This is a decree, lest one use a torn Min'al, or a half-Min'al.

Yevamos 103b: A Yevamah came to do Chalitzah. Rav Yosef told Abaye to give the Yavam his shoe; Abaye gave him his left shoe.

Rav Yosef: Chalitzah with a left shoe is valid b'Di'eved. It is not l'Chatchilah!

Abaye: The same applies to a shoe that is not the Yavam's!

Rav Yosef: I intended that you let the Yavam acquire your shoe.

Rishonim

The Rif and Rosh (Yevamos 33b and 12:9) rule like Rav Yosef.

Nimukei Yosef (32a DH Mitzvas): 'Ekev' is all that keeps the foot inside, including the (back of the) heel and the sole. Rashi mentioned the sole to disqualify even if a small amount of the sole near the heel is Pasul.

Nimukei Yosef (33b DH Masnisin): L'Chatchilah, one may not use a big or small sandal, lest one use one that is too big for him to walk in, or does not cover most of his foot, which is Pasul.

Rambam (HilchosYibum 4:18): If the Min'al had no heel, or was too big for him to walk in, or small and did not cover most of his foot, or torn and did not cover most of his foot, or Nifchas that does not hold most of the foot, the Chalitzah is Pasul.

Ha'Emek She'alah (Vayikra 88:12): Shabbos 141a says that some Min'alim are hard and cannot be laundered. I.e., one cannot rub the sides on each other. Even a hard Min'al fits the foot well. A sandal is hard and wide, and one cannot make it fit his foot so well. Alternatively, a Min'al has a hard part, i.e. the heel and sole. Rashi (Yevamos 102b DH ha'Nifras) says that 'torn' applies to a Min'al, and Pechisah (lopped) applies only to a sandal. A Mishnah (Kelim 26:4) discusses a broken Min'al! We must say that at the heel and sole, it is like a sandal.

Rambam (19): If the sandal did not belong to the Yavam, or was big but he could walk in it, or was small but covered most of his foot, torn but covered most of the foot, or Nifchas and holds most of the foot, the Chazakah is Kosher.

Magid Mishneh: The Rashba says that mid'Rabanan the Yavam must own the sandal. This is a decree lest he use a sandal that is too big or too small.

Chasdei David (Yevamos 12 DH Choltzah): Surely, Chalitzah with a sandal Nifchas is Kosher. There is no concern lest one use such a sandal that does not hold most of the foot, for it is hard and one cannot wear it if it is missing so much. A torn Min'al is a bigger Chidush. Even though it is feasible to use a half-Min'al, we do not decree, since the Min'al covers most of the foot.

Rosh (3): We decreed against Chalitzah with a Min'al, lest one use a torn Min'al. In Shabbos (141a) we say that Chalitzah with a torn Min'al is Kosher! That`` refers to when it is not torn so much and he can walk in it. Nowadays, we do not have sandals, so we use a Min'al l'Chatchilah.

Yam Shel Shlomo (Yevamos 12:14): The Rosh, Tur and Tosfos hold that one cannot walk in a torn Min'al that does not cover most of the foot. Therefore, it sufficed to disqualify a (small) Min'al that does not cover most of his foot. They did not need to additionally teach about a torn Min'al. The Rambam disqualifies a (Min'al that he cannot walk in, e.g. a) torn Min'al that does not cover most of his foot. This implies that if he can walk in it, it is Kosher even if it does not hold most of the foot! What is his source to be lenient?! Rather, we may not infer this. He merely cited the Beraisa.

Poskim

Shulchan Aruch (EH 169:14): L'Chatchilah, the shoe for Chalitzah should be given to the Yavam for a gift.

Beis Yosef (DH v'Yitnu): The Mordechai (119) says that if the shoe is designated to be used for Chalitzah, they need not give it to the Yavam for a gift. The other Poskim do not make this distinction.

Beis Yosef (DH u'Mah she'Chosav Af): Even though we give it to him with intent that he return it afterwards, a gift on condition to return is a valid gift.

Be'er Heitev (16): The Maharshal (90) says that if someone else gives his shoe, he gives it to the Rosh Beis Din, who then gives it to the Yavam. Seder Chalitzah (39) says that the owner gives it directly to the Yavam.

Shulchan Aruch (ibid.): Some say that he should walk in it a bit so it will appear like his.

Gra (51): The Mordechai (Yevamos 57) requires this in order that we will see if it is the right size for his foot.

Rema: If they did not give it to him, it is Kosher.

Shulchan Aruch (21): The sandal should correspond to the size of his foot, not too big for him to walk in, or too small and does not cover most of his foot, or was torn and he cannot walk in it.

Be'er Heitev (24): If a Min'al is big and folds over onto the back of his foot, one may not use it l'Chatchilah even if he can walk in it, lest one use one that he cannot walk in. B'Di'eved, it is Kosher if he can walk in it.

Shulchan Aruch (22): If the sandal was too big for him to walk in, or small and did not cover most of his foot, or was torn and he could not walk in it, or it has no heel, the Chalitzah is Pasul.