Most model servos should be powered with 4.8V to 6V. so the '7-8V' NiMh may be powering the servo to a point where it is not destroyed, but working beyond specification. That may account for its wrong behaviour.
This is a datasheet for the Hitec HS-422 servo (it isn't ideal as it is from Sparkfun, and not the manufacturer, but better than nothing). It states the operating voltage range is 4.8-6V.
It states a no-load current of 180mA. So as the motors are effected by the servo running, either the battery isn't capable of supplying enough current (maybe a NiMh PP3?), or it has quite a significant stall current, or the servo is damaged.
It may be that the voltage drop of the LM298 (which drops quite a lot of voltage) and a lowered voltage caused by the servo is so low that motors stop working.
You need to get a multimeter to try to understand what is happening. Try to measure the voltage across the motor drivers when the servo is disconnected.
Turn on 1, 2, 3, then 4 motors, and measure the voltage each time. If the voltage is dropping by more than, say, a volt, then the battery supply may not be sufficient for the motors.
Try the same test with the servo included. Again, of the battery is dropping more than a volt, then the supply may be inadequate.
If you have access to a good bench power supply, capable of supplying all 4 motors + 1A, then try that and observe the results.
The easiest short term fix may be to try powering the servo only directly from its own 4xAA battery supply. If things start working a bit better, then the problem is servo power. If the servo is still not sweeping, you may have broken it.
In either case, the servo should not be powered directly from the '7-8V' battery. It should be powered from a 4.8-6V supply. If you have enough space and load capacity, use 4xAA. Otherwise use a linear or DC-DC voltage regulator.
Edit:
If you plan on using a higher voltage LiPo then use a DC-DC switch mode power supply to generate the servos 6V.
If you stick with NiMh '7-8V' then either will be okay, and the wasted energy using a linear regulator (where the excess power dropping down to 6V is turned into heat) is acceptable. If you choose a 6V linear regulator with a voltage drop of 0.7V or less, then it should keep within 4.8-6V for most of the NiMh supplies discharge.