The key thing (as I understand it) is that each process naturally has a relatively small private set of data, so Erlang can use a stop-the-process semispace copying collection strategy and it's fast enough to work out fine.

Since nothing can be writing to it during that anyway, I'm not sure the language level immutability makes a lot of difference to GC itself.