1407, padell "small spade," from M.L. padela, perhaps from L. patella "pan, plate," dim. of patina. Meaning "short oar with a wide blade" is from 1624. As an instrument used for beating clothes (and slaves, and schoolboys), it is recorded from 1828, Amer.Eng.; the verb meaning "to beat with a paddle, spank" is first recorded 1856. Paddlewheel is from 1805.
"to dabble, wade in water," 1530, probably cognate with Low Ger. paddeln "tramp about," freq. of padjen "to tramp, to run in short steps," from pad (v.). Meaning "to move in water by means of paddles" (1677) is a different word, from paddle (n.).