What is the maximum clock frequency the PROM can accept and still output data reliably?
This information is documented in the PROM data sheet. See the TCYC specification for the respective part under:
AC Characteristics Over Operating Conditions for XC18V04 and XC18V02
AC Characteristics Over Operating Conditions for XC18V01 and XC18V512
(Check the TLC and THC specifications to calculate duty cycle requirements.)