Hmmm ... after quite a bit of experimentation, including setting a custom paper size to 12.95" x 19" (a valid choice, according to Epson's documentation), as well as using the built-in "A3+ Borderless (retain size)" size setting, I can't get past a printer error message which complains that borderless printing isn't supported for the selected media size. Naturally, it can't be ignored - the only option is to cancel the print job.
I believe that borderless printing of 13 x 19 Velvet Fine Art paper using a P800 is broken due to bugs in Epson's software.
I've tried loading Velvet Fine Art media via the sheet feeder (to do this, I have to tell the idiot Epson software that I've some some other kind of matte media loaded). This seemingly works, but is an obvious kludge. I'd go with the straight-through loading method, which is a lot better designed than the manual feed tray ... except that Epson's software insists that this option is only available for their Enhanced Matte poster board.
I'd like to conclude by saying something positive about Epson's software, but I'm having trouble being more positive than to say "it usually works". It's far from elegant. This seemingly minor issue has chewed up far too much of my time, and I still don't have a satisfactory solution other than going back to the 3800.