Implementation of built-in function Fold

It's quite easy to show that Fold doesn't use the memory that would be required to store intermediate results.

$HistoryLength = 0;
big = Range[1*^7];
ByteCount[big]
MaxMemoryUsed[] //N

40000124

5.49458*10^7

Fold[# + 1 &, big, Range@100];
MaxMemoryUsed[] //N

1.34909*10^8

FoldList by comparison (with a much shorter Range):

FoldList[# + 1 &, big, Range@30];
MaxMemoryUsed[] //N

2.49489*10^9

You can implement Fold without having to create an intermediate list. The documentation probably mentions that just to make the relationship between Fold and FoldList clear. For example, consider this simple construction of a Fold operation:

myFold[func_, x_, list_List] := Module[{f},
    f[a_, l_List] /; Length@l >= 1 := f[f[a, First@l], Rest@l];
    f[a_, {}] := a;
    f[x, list] /. f -> func
]

Now try it:

myFold[f, a, {b, c, d}]
(* f[f[f[a, b], c], d] *)

This is exactly what Fold would return. This and J. M.'s hint on TracePrint should make the implementation clear.