いってらっしゃい consists of 行って+(い)らっしゃい
いらっしゃい is probably the 連用形 form of いらっしゃる
which comes fromいらせらる
which consists of いら, せ, and らる
いら comes from いる(入る: enter)
せ and られる both show respect.
いらっしゃる is a respect form of 行く(go), 来る(come), or 居る(be)
どこへいらっしゃるのですか?(where are you going?)
先生がいらっしゃった(The teacher has arrived)
明日は家にいらっしゃいますか?(Will you be home tomorrow?)
FYI: おっしゃる(say) comes from おおせある consisting of おおせ and ある