Фамилия Войличенко образована от прозвища предка Войлич. Скорее всего, это прозвище указывало на профессию: валяльщика войлока. Войлок — плотный нетканый материал из спутанной овечьей шерсти. На Руси таких мастеров называли шерстобитами или шаповалами, а прозвище Войлич (от «войлок») закреплялось за человеком по роду его занятий.

Фамилия построена по распространённой украинской модели: к основе Войлич- добавился патронимический суффикс -енко, означающий «сын» или «потомок». То есть Войличенко — буквально «сын Войлича». Такие фамилии особенно типичны для левобережной Украины и исторически были распространены среди казачества и крестьянства.

Прозвище Войлич со временем вытеснило личное имя предка и стало наследственным — сначала в быту, а потом и в официальных документах. Стоит заметить, что в русском языке есть и похожие фамилии: Войлов, Войлков — они образованы от того же корня, но с помощью других суффиксов. Однако именно форма Войличенко однозначно указывает на украинскую среду бытования и профессиональное происхождение от валяльщика войлока.