No te preocupes por los MHz del PIC, incluso un PIC sencillito trabajando a 4MHz será suficiente.
Hagamos unos cálculos rápidos.
Imaginemos que la rueda es muy pequeña, por ejemplo, con un radio de 20cm.
Eso daría un perímetro de: 1 rev = 2 * PI * 0.2 = 1.25664 m.
Imaginemos que vas a rodar a supervelocidad, por ejemplo, a 500Km/h.
Tu rueda da estas vueltas por Km: 1000 / 1.25664 = 795.77
Y por tanto, da estas vueltas por hora: 795.77 * 500 = 397886.43
Traducido a RPS (revoluciones por segundo): 110.52
Un PIC de la familia 16F trabajando a 4MHz es capaz de procesar 1MIPS = 1 millón de operaciones por segundo.
O sea, que entre una revolución de tu rueda y la siguiente, el PIC podría ejecutar: 1000000/110.52 = 9048 instrucciones.
Vamos, que en un caso límite, al PIC le daría tiempo de fumarse un puro entre vuelta y vuelta...