So I'm rank 58, which I think is already almost half-way through the game, and I still haven't unlocked any new cars.
How do I do it? I thought wasting cars should unlock them, but that's what I usually do most my races (the times when I don't go batshit insane and decide to hunt down every last ped), but still no cars unlocked.

It's random, for ex. even on rank 1 I never unlocked Don Dumpster or Ivan the Bastard cars but ED101 and Vlad were first to be unlocked and Otis car was the last, well maybe before Psycho Pitbull on Blood on the Rooftops which is somewhere near rank 9. Chances are 50/50. Also manual is misguiding because BELOW means less number in the rank, not bigger, as you go from ABOVE (99) to BELOW (1). So:

rank 89 or below - Vlad, Ed-101, Mech (rank 89 or 88, 80, 75...)
rank 55 or below - Screwie Lewie, Ivan (rank 55 or 54, 50, 45, 40...)
rank 38 or below - Psycho Pitbull, Otis (rank 38 or 37, 35, 30, 25...)
rank 21 or below - Don Dumpster (rank 21 or 20, 15, 10, 9, 1...)
rank 9 or below - The Suppressor (Special forces APC) (always stealable when wasted, race is unlocked at rank 9 and it's so damn immune to damage - think Police car 2x or 4x armor or 8x ~ 10x Psycho Pitbull I always run out of time wtf).

Or just finish the game, it will unlock all cars, even that pedestrian electrocution car.

You can also use cheats. On the race screen, type KEVWOZEAR.

I've played this game over and over and over and I've yet to come across a car that handles even REMOTLY as good as the Red Eagle. Point being, while snagging different cars is cute, ultimately they aren't that useful.

Then you've never got the Suppressor. That thing is unstoppable once you've fully upgraded.

Oh I've driven the Suppressor. XD You can't see where the hell you are going in that damn thing!

I'm pretty sure Mech can't be stolen until you're rank 55. Before rank 55, I made sure he was in every race, wasted him every time but never got his car. I actually got his car after I got Screwies and Ivans. I'm guessing you were stuck with a combination of the 3 cruddy steal worthy cars. Ed 101's car is a good racer if you're chasing checkpoints. Screwie's car seems to be a hit or miss with some people, I like it but I know not everyone does. Pitbull and Otis are both excellent smashers with stellar handling, both handle better than the Red Eagle. Don Dumpster would be better if he didn't pop wheelies all the time. If you want to have any success controlling him, you have to tap your accelerator otherwise you wheelie and spin all over the place.The rest of the cars are crap though, Vlad can't steer, Ivan can't be controlled and Mech can't stay on the friggin ground.

In the splat pack, you still get the good vehicles mentioned above. I just unlocked Stig's car at rank 67 and I'm quite impressed with it. It's a decent smasher with great handling, feels like the Pitbull and the Red Eagle had a baby. Thing is, the suppressor doesn't become stealable until the game is practically over. At rank 9, you might as well just finish the game to get it cos getting it before then is a total pain and just ain't worth the effort.

Then you totally lost the point of the game. It's not to win races and beat the game it's to have mindless fun smashing into things, who cares if it's near the end of the game when you face the Suppressor (got it on my first try btw when I first played the game back in the day) the vehicle is fun to drive, even underwater. Go up against the Cop APC's with it and you'll see what I mean.

What? Where did I say that the point of the game was to win races? I never said anything of the sort. All I said was unlocking the suppressor at rank 9 isn't worth the effort when all the cars are unlocked after you finish the game anyways.

Anything less then full speed head on collisions using Don Dumpster's vehicle won't even put a scratch in the suppressors paint job. Then you have the problem of losing sight of the supressor (it doesn't show up on the map) causing you to find out where he went. Then when you do, you have to get far enough away from the supressor to do a full speed head on collision, there's a high chance of the supressor ramming you before you're ready (Dumpy's vehicle doesn't exactly have stellar handling), one of the nomrals squad cars can ram you, the supressor turns and avoids you or you hit the sides or rear for no damage,or it teleports away. If you find a solid granite car power up, you only have 30 seconds till it runs down, will you find the supressor and waste it in that time? If that's fun to you, knock yourself out, I personally just can't be bothered, especially when it's available after you finish the game which isn't far away. If you say you got it on the first try, you must have either fluked, used cheese or you have the patience of a saint.

With so many factors against you, I stand by what I said. Yes, the suppressor is fun, but trying to waste it isn't. Better to just get it when you finish the game.

I'm having trouble getting this cheat to work. Can you give me a bit more detail. Honestly, I like Carma, but it does get kinda grindy at times. I dont want to keep on running the same god damned tracks all the time.

You need to enter this cheat on the screen with a race name, like Maim Street. Just start new game, pick a driver and difficulty and after the cutscene you can enter the cheat. If you hear a sound, everything should be unlocked.

Okay, I got it working. The cheat has to typed in while using the default control settings. Thanks for your help!