According to this article in Japanese WP, - is the descendant of Middle Japanese - (-tasi), which ultimately traces back to Old Japanese (or Proto-Japonic) (itasi; "sore, acute").
A paper referred by that page argues that this form has changed its meaning taking the path of "painful" → "sorely felt" → "of physiological necessity" → "of emotional necessity" → "desire".
> _Someone proposed it might be from -te + ai, love_...
It's unlikely to be true considering the oldest attested form of this word ended in -asi, not -ai. Additionally, if Japanese speakers want to incorporate Chinese words in such a way, they never use _te_ -form but append them directly to word stem or . For instance, - in {}{} is said to originate from {} ("appearance").