全然 + ない is part of a series of pairings where a word at the beginning of a sentence is paired with a specific verb conjugation or phrase at the end of the sentence. My professor told me the linguistic term for this but unfortunately I can't remember it at the moment. He also told me that one of the theories as to why Japanese does this is that in long sentences, you're sort of giving the listener an idea of what is coming at the end (the verb tense).
Another example of a pairing that seems a bit redundant:
危なく + [verb]ところでした : almost did [verb]
In this usage, 危なく means "almost did" rather than "dangerously" (which was my first instinct), and [verb]ところでした also means "almost did". Though perhaps the 危なく implies that the activity that was almost done is undesirable?
I'm sure I know more of these pairings, but I can't think of them at the moment. If anyone can remind me of that linguistic term I mentioned, I would appreciate it; I think it is [something]ぶし, むし, or some u-sound + し? I'm not sure haha.