Apparently, what we now call an icicle in English was originally referred to as simply a gicel in Old English, which became ikyl or ikel in Middle English, and later ickle.
At some point, people began adding is, the Old English word for ice, to create the redundant is ikyl.
By the 14th century, this was compounded into the word icicle.