Think of the following:

count = 0
for i = 1 to n:
  output[i] = do_something(input[i])
  count++

Clearly, this is breaking the problem into smaller pieces. But it's a pain to distribute, because count is shared between all the loops.

The map-reduce paradigm enforces certain constraints, among them that the functions must be idempotent (which is a fancy way of saying they can't have side effects, like using a shared count variable). It turns out that any code following these constraints will be to some degree distributable.

So the advancement here is not the creation of map or fold functions, but rather the observation that certain types of maps and folds are easier to distribute than others while still remaining useful in a variety of contexts.

(As you probably know, there are debates about whether this was really "discovered" by Google or had been known for a while. Whoever invented it though, it's reasonable to say that it's a non-trivial observation that many problems can meet the M/R constraints, and hence are easily distributable.)

I think you've hit the nail on the head with your comment.

It's not true that in any functional language maps can be parallelized - the language must be pure. (I believe Haskell is the only vaguely mainstream purely functional language. Lisp, OCaml and Scala are all non-pure.)

We've known about the benefits of pure code since even before timesharing, when engineers first pipelined their processors. So how come no one uses a pure language?

It's really, really, really hard. Programming in a pure language often feels like programming with both hands tied behind your back.

What MR does is relax the purity constraint somewhat, and provide a framework for other pieces (like the shuffle phase) making it quite easy to write distributable code for a large fraction of problems.

I think you were hoping for an answer like "It proves this important sub-lemma of $NC=P$" and I don't think it does anything of the sort. What it does do is show that a class of problems known to be distributable are "easily" distributable - whether that's a "revolution" in your opinion probably depends on how much time you've spent debugging distributed code in a pre-Map/Reduce world.