It is true that persistent data structures are slower than their mutable counterparts. There is no dispute about that. Sometimes the difference is negligible (iterating over a linked list versus an array), other times it can be big (iterating in reverse), but that's not the point. The choice to use immutable data is (or should be) a conscious one: we're trading performance for stability.
Consider this point: for most (not all) modern programs, local performance is not a concern. For today's programs, the real performance bottleneck is in parallelization - both on local machine with shared memory, as well as across different machines. With the amounts of data we're processing these days, squeezing every last bit out of memory locality and branch prediction isn't going to cut it. We need scale. And guess the number one source of bugs in parallel programs? That's right - mutation.
Another big concern for modern programs is stability. Long gone are the days when a program could crash on you, and you just restarted it and kept working. Today's programs need to work on headless servers, without human intervention at all, for months or years. Today's program can't just throw up its digital arms and expect a human to figure out what went wrong. In this setting, local performance is so much less important than stability and parallelization: it's much cheaper to buy (or rent) another ten servers than to hire a human for restarting the program every now and then.
It is true that one can make a parallelizable and stable program using mutation. It is theoretically possible. It's just way harder. With immutable data, you have to actually aim at your foot first.
And then, here's some perspective: we've already been there. How often do you use the goto instruction in your code? Have you considered why that is? You can do all kinds of neat performance tricks with goto, and yet we choose not to. At some point in programming history, we have decided that goto was more trouble than it was worth. Same thing happened with raw pointers: many languages don't have them at all, others have them closely guarded, and even in those languages that have unrestricted access to raw pointers, it's now considered kind of a bad form to use them. Today, we're in the middle of the next stage: first we gave up goto, then we gave up raw pointers, now we're slowly giving up mutation.
However, if you really find yourself pushing the envelope of local performance for a legitimate reason, and you have determined that the immutable data is indeed the bottleneck (remember: first measure, then optimize), then most functional languages (except Haskell and Elm) will let you get away with mutation, albeit reluctantly. Just like raw pointers in C#, you can have mutation, you just have to be explicit (and careful) about it. In F#, for example, you can have mutable variables, raw arrays, mutable records, classes, interfaces, etc. It is possible, just not recommended. And the general consensus so far is that it's OK to employ mutation as long as it's localized (i.e. does not leak to outside), and you really know what you're doing, and you've documented it, and tested it to the death.
A common case for this is "value construction", where your have a function that ultimately produces an immutable value, but does all kinds of messy stuff while doing it. One example is how F# core library implements List.map: normally, because lists are iterated front-to-back, but constructed back-to-front, one would need to first construct the transformed list by iterating, and then reverse it. So the F# compiler cheats here and mutates the list as it's being constructed in order to avoid the extra reversal.
And another note on the "locality" concern. Remember how I mentioned that you could do all kinds of neat performance tricks with goto? Well, that's not quite true anymore. Since the programmers started writing programs without goto, the binary code became more predictable, because jumps are now generated by compilers, not coded by humans. This made it possible for CPUs to, well, predict them, and optimize processing based on these predictions. The end result is that now you're actually likely to get worse performance by indiscriminate use of goto than by using accepted higher-level tools like loops. Back in the day, CPUs couldn't afford to be that smart, so that the choice to not use goto was purely a stability measure. But now it turned out to be actually helpful with performance, who would have thought?
I submit that the same thing will happen with immutability as well. I'm not sure exactly how it will happen, but I'm sure that it will. Even today, without special hardware, it is still possible to do some optimization at compile time: for example, if the compiler knows that a variable is immutable, it may decide to cache it in a register for a long period, or even promote it to a constant altogether. It is true that most actual compilers today don't perform all of these possible optimizations (though they do perform some), but they will. We're only just beginning. :-)
I know and appreciate those design goals of functional languages. My question about good move semantics in typical functional languages would support that goal, not contradict it. Done properly, I believe it could allow a purely functional style of programming that translates exactly as the corresponding imperative program would, and execute just as fast.
You can even have mutation of various sorts in Haskell. The sanctioned versions are in IO, ST, and STM, but those are not the only ones available. If you're sufficiently careful, you can use things like unsafePerformIO to implement seemingly immutable structures with mutation under the hood. If you want to live extremely dangerously, you can even crack open the IO or ST types and manually handle state tokens with realWorld# or even runRW#. Such code can be safe, but requires great care and attention.