From The Barnhart Dictionary of Etymology (the definitive work):
"Before 1338 tikellen, in Mannyng's Chronicle of England; of uncertain origin. The Middle English word or even a remote form of it is not recorded in Old English, though the sense is found in Old English tinclian to tickle (cognate with dialectical German zickeln to tickle). Various possibilities have been suggested, the most plausible being that tickle is a frequentative form of t i c k to touch lightly (with -LE), although the chronology does not favor this theory. Another, yet more complex, possibility sometimes given is that Middle English tikellen represents an alteration (by metathesis of k and t) of kittlen (probably about 1475 kytill), implied in Late Old English in kitelung tickling; compare German kitzeln tickle and Old Icelandic kitla to tickle."
Hope that helps.