I figured out the root to all of my problems... and it kinda sucks until I can find or make better code. Basically my code was perfectly fine... However, my encoders aren't perfect. When the code sets a speed above a certain threshhold, I think that the encoders begin to freak out (probably because of their resolution) and cycle between random increments. So for now, in order to practice, all we have to do is set the speed of the motors to a lower setting.
In your encoder handling code, are you using interrupts to detect rising edges from the encoder pins? If not, I suspect the reason you can't accurately track high speeds is that your control loop doesn't run fast enough to catch all the rising edges. The control loop frequency should be the bottleneck far sooner than anything mechanical or electrical in the encoder because the control loop likely has hundreds of instructions (clock cycles) to go through each time, whereas most quadrature encoders' outputs are asynchronous and really fast.
For example, if one has a motor running at 6000 RPM or 100 rotations per second and the encoder has 100 pulses per rotation, there are 10,000 pulses per second (10kHz) that the microcontroller must detect perfectly. With a typical Arduino running at 16Mhz, this means that one can fit (very roughly) 1,600 processor instructions maximum per control loop before expecting losses. Keep in mind that 1 line of C++ can translate into many processor instructions after compilation. This post
suggests that Arduino's digitalWrite and digitalRead take around 50 clock cycles each (the convenience of the functions comes with the cost of considerable overhead). Also, the period of the 10kHz encoder pulses is 1/10000=0.1 ms, so if you have any sort of delay() calls that stall the control loop on the order of milliseconds, you can abandon any hope of tracking the encoder accurately. (instead of delay, look at millis() or micros())
One can do the math in a more indirect way too: If you want the car to go 5 m/s but want your encoder configured to have 1mm resolution (1mm per pulse), then at max speed, the encoder will be sending 5/0.001=5000 pulses per second. This translates to 3,200 clock cycles max or a period of 0.2ms.
The best solution that should guarantee accuracy is to use interrupts
to track the encoder pulses. The link has more detailed info, but basically an interrupt enables dedicated electronics to listen for a rising edge (or other types) on a certain pin and literally interrupt whatever the arduino was doing and enter a function of your choice before returning back to what it was doing. In the case of encoder reading, this function probably checks if it should increment or decrement an encoder position variable. The advantage is that interrupts trigger exactly when you want them to and get out of the way of your control loop otherwise.
Since interrupts rely on special electronics, only two of the pins on a typical Arduino are interrupt capable. Fortunately, quadrature encoders only have two wires to listen to, so it works out. I would also suggest looking at this encoder library
which is optimized for interrupts, saves you some work writing the code, and would probably be more reliable anyway. I've used it before for a simple knob but I think it'd work well for this high speed stuff.
Sorry this went went so in-depth, and maybe you're already using interrupts. Nevertheless, I think it's interesting and I hope it's helpful to others.