Note that the "up arrow" referred to in the song is not the current up arrow on the cursor keypad. Some early versions of ASCII-ish had an up arrow where the caret is now. And telnet actually mostly used control-], not control-^ anyway. I seem to recall Steele saying that he used "up arrow" because it worked better in the lyrics. I heard Steele sing this once and I think I recorded it.
No, not exponential. The escape sequence is: <newline> then '~'. Anything after the '~' is special. In other words, only the first '~' appearing directly after a new line is special.
For example, <newline>~~~~ will send <newline>~~~ to the remote side.
You need to enter ~ after pressing return (or else you have a bad time editing command lines involving home directories), so in practice only the first ~ each SSH instance sees needs escaping.
It's convenient there (and probably not accidental!) that Unix usernames are usually lowercase, so if you want to run a command like
~otheruser/bin/cat
it won't conflict with an ssh escape sequence (although you won't see the ~ appear until you've typed ~o).
On the other hand,
~Randomuser/bin/cat
would be impossible to type immediately at a new command prompt over an ssh connection (though of course it's possible to run such a command by typing anything such as "x<Backspace>" first).
Isn't it exponential? To escape ~, you need ~~. To escape ~~, you need ~~~~. To escape ~~~~, you need ~~~~~~~~. Etc.