Immutability is something that happens at the level of the programming language. Runtime efficiency is a concept that, unsurprisingly, lives at runtime.

When eg a Haskell program runs, its supposedly immutable datastructures get mutated all the time. For example laziness is one way that happens.

Another example is that a (pure) Scheme program will overwrite the same memory addresses over and over again while it is running, just like a C program would. Conceptually, no mutation happens, it's just that the garbage collector constantly frees up memory that will be get re-used immediately.