Has anyone done a board with more than the standard 2-sides?

I am working on a board design (details to appear later - it's getting close) and I am concerned about component density and the ability to route the board. A previous version of the board pretty much maxed out component count and took several weeks (albeit rare spare time) to hand route (the autorouter I was using at the time just utterly gave up.) This new design, even with all the random logic and some of the higher-level logic crammed into 12 GALs, exceeds the pin count, my measure of board density, of the previous version by nearly 30%. So, it is looking quite likely that I'll need to go to at least a 4-layer board to be sure it can be routed with the chips as close to each other as I believe they will need to be.
Has anyone used KiCAD to do 4 layers?
Does the Chinese company I have seen used for many of the recent boards do 4 layers?
What precautions, tips or best practices should I be aware of?
Any input from this great group would be much appreciated!

Thanks!

Bob Bell