There are PIC24 & dsPIC33 models with 512KB flash.
PIC18F8622 & 8722, and some other PIC18F's (87J50, 97J60, for example) have external bus interface, you can put a parallel flash (29xx-type) there, and the external bus can address up to 2MB.
From the datasheet, we can see that this can be used to store program code:
The External Memory Bus (EMB) allows the device to access external memory devices (such as Flash, EPROM, SRAM, etc.) as program or data memory.
Using other types of interface to connect to an external flash might be problematic as you would not be able to run the code from the flash directly, instead, you'd have to copy the code into RAM before running it - but since these microcontrollers have extremely limited RAM resources, this would severely limit the usefulness of such a solution (you'd have to implement some kind of paging/overlay technique).
Here's Microchip's product selection tool, allowing you to search for models with certain features: http://www.microchip.com/maps/microcontroller.aspx