I think there are a few possible origins:
- 「ない」＋接続助詞「て」＝「ないで」 (voiced due to proxomity)
None of them are completely satisfying.
「で」 being the 連用形 of 「だ」 is a fairly recent reanalysis, but I can't find any traces of 「ないで」 before the Meiji period, so in theory it's possible this is how it was created.
You could also group 「なき」＋「なり」の連用形「に」＋接続助詞「て」 here.
However, this theory really does not make much sense to me. Having the copula after 助動詞 is not seen anywhere else.
I'm somewhat willing to buy this theory because 接続助詞 are usually pretty relaxed about what they can come after. But in general, the 接続助詞「て」 comes after a 連用形, so it's not exactly like this should be bought without some good evidence.
It's possible, but as far I know, 格助詞「で」 only connects to nominals. Seems weird for it to connect to a 助動詞. Maybe there is a dialect where this is allowed that 「ないで」 was borrowed from?
This being essentially the same as the last one, but happening at an earlier point in time.
Syntactically it is slightly more believable because 「に」 connects to things other than nominals (e.g., 「ずに」), and the 連体形 is quasi-nominal anyways.
Though, since 「ない」 as a 助動詞 is AFAIK fairly new, I'm not so sure of the probability of this one.
However, I was looking through older texts, and there are a number of instances of 「なきにて」 in the 源氏物語. Here are a few:
I am not entirely sure what these are, as 「なき」 seems to be connecting to the 連用形 of the former verb instead of the 未然形 as we see in modern language, and I have also never heard of 「ない」 being used with verbs so early on. Maybe one of our historical Japanese experts can help me out (@Dono?).
So is it a te-form?
Well, depends on what a te-form is.
If you consider a te-form to be something which people synchronically believe has a 接続助詞「て」 in it, then no, because I don't think that's how people think of it morphemically (it is not even listed as a theory in any dictionaries!).
If you consider a te-form to be something which diachronically includes 接続助詞「て」, then almost certainly, because as you may have noticed, all 4 theories have 「て」 in them from the historical perspective.
If you consider a te-form to be defined syntactically, then kind of. 「ないで」 plays some of the syntactic roles that a positive te-form would play (supports 補助動詞, stative adjuncts), while 「なくて」 plays others (conjunction). If you consider 「なくて」 a te-form given this definition, I would also consider 「ないで」 one.