1530s, put together hastily," probably from Middle English shovelen "to move with dragging feet," itself probably a frequentative form of shoven (see shove (v.)). Or perhaps from Low German schuffeln "to walk clumsily, deal dishonestly."
Of playing cards, first recorded 1560s. Meaning "walk slowly without lifting the feet" is from 1570s. Meaning "push along gradually" is from 1560s. Meaning "move from one place to another" is from 1690s. Meaning "do a shuffle dance" is from 1818. Related: Shuffled; shuffling. Shuffle off "get rid of, dispose of" is from Shakespeare (1601).