How does PWM work in the Arduino?
You might find the AVR131: Using the AVR’s High-speed PWM
application note useful.

Let's be clear on a couple of points regarding PWM.

A fixed frequency pulse train is generated.
The pulse-width is modulated (adjusted) so that the on-time varies from 0% to 100% depending on the &quot;analog&quot; value fed to the PWM register.

Let's say you want a PWM with a resolution of 256 steps.

The PWM counter is reset (to zero) at the start of each PWM cycle and the output is switched high.
A counter starts counting at a rate determined by the PWM oscillator and configuration registers. This count value generates the ramp shown in Figure 2-2.
When the counter exceeds the OCR threshold value the output is switched off (but the counter keeps on going to 256).
On the clock pulse after 255 the counter rolls over to zero, it resets and the process starts again.

It should be clear by now that the maximum possible PWM frequency would, in this case, be CPU clock / 256 but it may be much lower due to other divisions, etc., in the PWM controller.
So, to answer your questions:

But I can't seem to understand how does PWM wave fit inside the input window of PWM pins.

The beauty of PWM is that the output is either fully on (high or 1) or fully off (low or 0). This makes it very easy to implement with digital logic. There is no waveform inside - only binary counters and binary comparators. It is the average value of the output that gives the analog output.
This can work digitally to, for example, dim the backlight in your phone. The backlight is switched between fully on and fully off quickly enough that you don't notice the flicker and the brightness appears to be proportional to the PWM duty cycle. For a true analog signal - a voltage varying between 0 and 5 V, for example, then a simple RC (resistor-capacitor) low-pass filter may suffice.

As PWM pin's take input in every ~1-2ms how are PWM waves formed inside that input window?

Hopefully that's clearer now.

And Does the clock speed of crystal oscillator has anything to do in this process?

Yes. Everything will be based on that but usually after having been divided down by some power of 2 (4, 8, 16, etc.).