Aside from trying to implement computationally inexpensive compression/data packing strategies (such as run-length encoding, throwing away unnecessary data precision etc) there's only one other practical solution - choose another device!
(Unless you've got enough spare IO pins and don't need any speed whatsoever, in which case you *can* attach an external [FLASH/EEPROM] memory and write some driver functions to read/write data. Parallel devices are greedier on IO but will offer higher speeds, whereas serial (such as I2C EEPROMS) devices will be excruciatingly slow, but frugal on IO... I've used both approaches in the past, but the PIC family is sufficiently large and diverse now that choosing another device is probably the best option!)