Creating a quad-tree from world data is very very simple. It's even more simple if it's 2D since the bounding checks are just simple comparisons. Also if you provide links to left, top, right, and bottom neighbors whenever a unit breaches one of the current node's boundaries you just place it into the appropriate node's list. If you set these references at startup time then crossing quad-tree boundaries is a snap.
Too many units, too large a world:
This will likely cause you to have to split up the world into a quad tree for fast collision detection.