Musannaf Ibn Abi Shayba 16:692

Abu Bakr narrated to us, he said: Hafs narrated to us, from Abd al-Malik, from a cousin of Ubayd ibn Umayr: He said: Ubayd ibn Umayr used to begin by taking off the left [sandal/shoe], then he would take off the right, and he would place it upon the left.