The common feature of most examples of the word pad seems to be a sense of cushioning, as traced in some of the examples at etymonline:

http://www.etymonline.com/index.php?l=p

(though I note that Bartleby gives a slightly different etymology for the pad component of footpad to that offered in the first site, tracing it to words meaning path more directly:
http://www.bartleby.com/61/roots/IE394.html)