Impossible to vary square wave FREQUENCY output based on a PWM input?

It can be done purely in hardware. But in order to proceed, you have to tell us what is the input PWM frequency since it will determine whether the Arduino's 16 MHz clock is capable of processing and calculating the duty cycle of the signal. Another caveat is if you are using an UNO, the PWM output frequency will be limited since you'll be using one of the 8 bit timers for the PWM generation.

My solution would be to use the Input Capture Unit of Timer1 to calculate the incoming signal's duty cycle, and use Timer0 for the PWM output