Hmm.... thanks for pressing this, demerphq. You appear to be right about not needing so many mortals. I think the trick is to avoid incrementing any refcounts (as I was doing after hv_store()), and only mortalize the RV I am pushing on the stack. This is basically what you said, but the code comes out a bit different from what you said:
AV *arr = newAV();
av_push( arr, newSVpv("test", 0));
XPUSHs(sv_2mortal(newRV_noinc((SV *)arr)));
HV *hash = newHV();
hv_store( hash, "key", strlen("key"), newSVpv("test", 0), 0);
XPUSHs(sv_2mortal(newRV_noinc((SV *)hash)));
So I'm just creating all "intermediate" variables non-mortals, not incrementing any refcounts after av_push or hv_store(), using newRV_noinc(), and mortalizing just the RV that's pushed on the stack.
Does that seem right? Sure looks cleaner...