iterative copy-tree in lisp
RE: how to rewrite to make it more readable


Stop using c[a,d]*r. While I have a soft spot for them your code may be more readable via first, second etc.
Name the predicates of the cond statement. What are they testing for? Use flet or labels.
Perhaps name the setf blocks to make it more clear what they are doing.
Perhaps split the setf blocks into separate setf lines. I had to check the hyperspec to verify that in fact each one was evaluated sequentially. It would be clearer if they were explicitly sequential.


To summarize: 


improve naming  
make things explicit


Re: performance

Without having performance benchmarks I cannot tell how the above changes would change the performance of the code. I also noticed that you didn't specify a optimize declaration. That could be used to change performance.