The noun σανδαλιον (sandalion) means sandal (same word). It's a diminutive of σανδαλον (sandalon), which also means sandal (Greek diminutives don't always denote small versions but also individuals from a group: a single lamb is a little lamb). Both these words occur mostly in plural. Our noun σανδαλιον (sandalion) occurs in the New Testament in Mark 6:9 and Acts 12:8 only. A more common New Testament word for sandal or shoe is υποδημα (hupodema).

It's apparently a formal mystery where this word comes from but here at Abarim Publications we find it rather obvious that this word is Hebrew and was introduced to the Greek language basin along with the alphabet (see our article on the many Hebrew roots of Greek).

Greek has the tendency to stick sigmas in front of words, or leave them out when they come with them (see our article on the noun σειρα, seira, meaning cord or rope, for more of these strange with-and-without leading -sigma duos). That said, the Hebrew word for sandal is נעל (na'al), which is a word that exist across the Semitic language spectrum and relates to a widely attested verb that means to bind or lock in. The noun is also used to describe horse shoes and the verb is also used to describe the hobbling of camels. Here at Abarim Publications we would guess that our Greek noun derived from s-na'al.