The manual "Programming the 65816 Including the 6502, 65C02 and 65802" available from The Western Design Center has a chapter describing and giving the source code for a program called DEBUG16 that can perform disassembly and instruction tracing of 65816 machine code. I ported the code to the CC65 assembler and got the disassembler running on my Replica 1 computer which has been modified to support a 65816 CPU. I haven't yet got the trace code ported and debugged.
Details and a link to the source code can be found here on my blog:
http://jefftranter.blogspot.ca/2012/07/ ... trace.html