Regarding your question: To my knowledge, handicap is intended to be linear.
The observation that large handicap games tend to end with a large score difference is not necessarily true. A large difference in score is usually a group dying involuntarily, which happens in both high handicap and even games on a regular basis.
However, it is far less common to resign in handicap games. Regular games in comparison often feature a high score difference as well, but those games are usually just won by resignation.
Another thing to keep in mind is that the rank system in use may very well be wrong for larger rank differences. You can see this very clearly by just comparing the rank difference of various players in different rank systems. For instance, KGS ranks tend to be a little bit more spread out than EGF ranks.
This means that two players with a difference of 8 stones on KGS may be only 7 stones apart in EGF rank. Which makes you wonder which is correct - and unless you got a huge database of high handicap game results, you won't know which of the systems is closer to the statistical truth.
This leads to my final thought: The EGF rank system (along the European Go Database) clearly specifies the intended win percentage for certain rank differences, also taking into account handicap. According to their formula, it is linear. I believe that AGA uses a similar system, too.
Edit (2018): I have recently worked more closely with rank computations than I hoped, and there is one thing I want to add, described here (I should note that some other information on that page appears to be outdated or wrong, in particular regarding AGA rating).
The skill difference that is supposed to be balanced by handicap stones depends on the skill of the players. That is to say, a single handicap stone in a high level match has a lot more impact than it does in a game between beginners.
This can in fact be quantified: A handicap stone in a pro game equals around 300 elo difference, around 150 for high dan amateurs and only around 50 (!) for kyu players. This adds another dimension in how rank differences and stone differences between players interact.
By the way, these data also show that adding more handicap stones is linear at least up to 4.