答えは分からないですが、単なる推測です。
アイヌ語だと動詞の前にsomoを付けて否定文にしますが、somoは「違う」という意味にもなるようです。つまり、元々別義があった可能性もあるかなと思いました。
「ず」と「ぬ」でザ行とナ行が混ざっているのも気になりますね。単純に音が変わったにしても元はどちらだったのか…ナ行が元だとすると「去ぬ」と似ているようにも見えます。「はしたなし(はした+成し)」みたいに動詞由来の複合語として「去ぬ+成し」みたいな可能性はどうでしょう。
過去の「し」と「き」については別語が混ざったのではないかという説もありますが、別語パターンとすると日本語の起源についてポリネシア系とツングース系が混ざったみたいな話も想起されます。
無かった(nakatta)はその中に「無く、有った」みたいな動詞的な要素を見出だせる等、活用の振る舞いも気になります。
フランス語の否定文ne...pasでは、not ...at allみたいに強調語だったpasが強調機能を失って義務化したのですが、英語のdo挿入みたいに否定辞は他の要素と抱き合わせられやすいのかもしれません…が、よく分からないです笑
古文自体は読めますが体系的な文法の勉強から離れているので勘違いがあるかもしれません…
英語は存在の否定(be not)で非存在を表しますが、「在らぬ」「居らぬ」みたいな表現は日本語にもありますね。ロシア語では否定辞とbeが縮約した一語で非存在を表しますが、助動詞と形容詞どちらが先かとかも問題になりそうですね。