I did a bunch of GC testing with Om, the GC profile wasn't dramatically different than naive Backbone.js on TodoMVC which is also working GC by blowing away the DOM on every update.
Node cloning can be done fairly quickly if the bulk of the node data is shared. The `_tree` immutable tree library (https://github.com/drfloob/_tree#quality-metrics) has a 1,024 child-node benchmark. On my slow laptop, it can build 1024 node trees at ~10/second, and the performance appears logarithmic on node count (http://jsfiddle.net/9x7aJ/2734/). I found it fast enough for my client-side use cases, but Clojurescript's optimized branching scheme could probably be implemented to boost performance. And anyway, if 10ops/second isn't fast enough, `_tree.Tree.batch()` lets you temporarily bypass immutability if needed, making modifications much quicker.
Even with Clojure's sharing, it is still the case (as I understand it) that you're forced to copy all nodes between the root and any node that actually changed. A mutating approach doesn't have to do any copies; it can just mutate the interior node of the tree.
As an example of a degenerate case, imagine that your root has 10,000 children. If I understand correctly, any mutation to any object in the entire graph requires duplicating the root and the entire 10,000-element array.
I honestly have no idea if this would be an important issue in practice or not, I just wanted to mention it as a super-brief pro/con list of immutable data structures.