From a linguistic viewpoint, the negation isn't split, merely transformed immediately before final utterance. Ne is phonologically a single word, and historically a single syntactic structure, as is pas. Today ne . . . pas, while two words, is a single syntactic structure. The redundancy improves intelligibility, and the separation serves to delimit the verb or verbal. My French is passable, but I am not a native speaker, and will have to depend on parallels in English.
Two analogous structures exist in English: the progressive and the perfect. Applying each in turn to they go yields they are going and they have gone. In both cases the verb is encapsulated within a single auxiliary structure, as French verbs are encapsulated in ne . . . pas. Linguists write this as a transformation of something called a K-terminal string:
they + pres. + (be + ing) + go --> they + (pres. + be) + (ing + go) --> they are going
they + pres. + (have + part) + go --> they + (pres. + have) + (part + go) --> they have gone
You've got to have tense, and be takes tense, and the subject is they, so it's are. The verb is go, and all verbs take ing, so it's going. The structure (have + participle) works the same way.
The foregoing may look a little brain-damaged, but it's remarkably efficient. The whole rule for auxiliary in English (neglecting passive and subjunctive, which are sentence transformations) is:
Aux => (tense) + {modal} + {have + part} + {be + ing}
where the parentheses indicate that tense is obligatory and the curly braces indicate that everything else is optional.
So with two tenses, past and present, and five modals--will, shall, can, may, must--you can generate a pageful of ways to link a verb with its auxiliaries, including the more recondite forms such as would have been giving. Note that this rule doesn't link the whole verbal to the subject--that's a different animal called the s-form rule, which is applied over the auxiliary.
To negate an affirmative sentence in modern English, the transformation is quite simple: apply not after the first word in the auxiliary. It goes there because the auxiliary delimits the truth of the whole sentence, both in time and condition. In the cases of simple past and present, when you haven't got an auxiliary form for not to follow, you can put it after a be, but not a verb. You have to supply a do for the not to follow. If you simply apply the Do transformation to an affirmative sentence, that will emphasize its truth value, but a do followed by a not serves merely as a sort of pre-affirmation.
Pas du tout and similar forms like pas de problem don't negate sentences, so the structure ne . . . pas is not required. The postfixed emphatic pas is analogous to the prefixed English emphatic do, and the archaic use of ne without pas is analogous to archaic English forms like "Say not the struggle naught availeth."