The frequency that your encoder outputs has nothing to do with the PWM frequency you run your motor at, which (in addition) has nothing to do with how fast your motor turns.
PWM frequency is one of those weird things - you need to look at the motor, the h-bridge, and figure out what works. If you're running a really high quality motor (like a Maxxon or MicroMo), you can probably run at 20 KHz. For a cheap-o plastic gearmotor, you might try 5 KHz.
The thing that sets the motor speed is the duty cycle, which is the percentage of each cycle that the PWM pin stays high.
There is no direct formula between PWM duty cycle and output speed - if there was, we wouldn't need encoders. Write a feedback loop. For simple fixed speed, you can just use a simple feedback loop that compares the computed speed (from the encoder) with the desired speed, and increases or decreases the PWM duty cycle according to how far it is off.
If you want more complex speed control, with less oscillations, look up PID on Google.
The only kind of motor where you can be guaranteed a correspondance between the driving and the actual output speed (without some kind of feedback loop) is a stepper motor.