I ended up doing much the same thing in an old (2e) Al-Qadim campaign. Here is the long story of what I (Balthazar the 1st, Sultan of Taddabur, a dwarven shair15/merchant rogue 11/cleric 12) went through to found the city of Tadabbur:
After we defeated the evil badgal (Tisan the Arch-Geomancer for anyone familiar with Al-Qadim), we knew that she might not be dead forever, so I returned to her old fortress in the jungle after the other PCs left and build my wizard's tower on top of it to guard the lower ruins and catacombs.
Once I built the tower I realized that it was just me and my retainers who would be present in event she or her forces ever returned, so I decided I needed an army. Maintaining an army was too expensive on an adventurer's salary so I realized that I needed a city with a functional economy to provide me with both a ready-deterrent force (the city army, the temples and whatever adventurerers were living in the area) and cover its costs.
It took me 6 game years of extraordinary measures to get my city's population up to about 7,000.
First the tower was in the jungle so I needed to clear the land and I needed the funds to pay to clear the land. (That isn't cheap even for a 15th level sha'ir). I decided I needed to clear about a five-mile radius area around the tower to give enough space to live and to plant crops. To finance the clearing and have someplace to get rid of the wood I sold futures in the 5-mile radius of timer to the spelljamming illithids for shipbuilding projects (which they then used in a large shipbuilding program to challenge the Elven Navy). This sale netted me about 5 million gp in trade letters. This plus a previous diamond mining expidition gave me a total of 15 million gp to spend.
I spend the lion's share of that on hiring a builder genie and a dao work-crew to build my tower into a palace worthy of a sultan. (I didn't word my wish very well so this ended up costing me about 25 million for a truly unique magical palace). The palace itself was completed in 60 months thanks to the genies. The city however took much more work.
To get a population to come to someplace in the wilderness, I paid the genies about another couple of million to complete basic civic buildings, parks and sample homes. I then sent agents to every slave market in Zakhara and bought out every slave I could find that had any skills at all and was healthy, setting me back several million more. (By this time on another spelljamming adventure we had defeated a group of unknown beings living on a strange asteroid. The other PCs claimed the mighty magics contained therein, I claimed the entire several-mile nickel-iron asteroid. I then sold the asteroid's location to a dwarven citadel-ship for 25 million gp).
Once I had bought out the contents of the slave markets in all of the major cities, I freed them all in return for them each taking a plot of land to either farm or set up a trade. Anyone who was willing to farm received free peanut seeds and cocoa seeds (courtesy of a trip to Maztica). I then set up the Great Tadabbur Chocolate Company to buy the cocoa crop from the farmers and produce chocolate for sale as a luxury good to other cities. This arrangement garnered a significant profit for myself (due to my chocolate monopoly) and a smaller profit for the farmers. Another company I set up handled the export of woodwares which became our other main export. (Most of Zakhara is desert so hardwood goods earn a good profit.)
Lastly, I hired a miner genie to do a radial survey of the surrounding land for any useful mineral deposits in return for my freeing him from his magical bondage. We backed up the radial survey with divination and commune spells to make sure we found everything. The tiny gold mine we found played out after about 10,000gp, but the genie did find large copper deposits. The copper deposits brought modest profits but it also brought arsenic which poisoned the ground water required an expensive cleanup.
Disease became a problem quickly so I set aside plots of land and offered them to all of the great temples of the land to build temples in my city. I also offered them freedom from taxation in return for their help with my healthy-city universal healthcare project. I figured that epedemics are expensive and it is cheaper to pay the temples and physicians to provide good general healthcare than it is to pay the cost of an epedemic.
My other big paranoia was that if things went badly, my populace could be induced to rise up against me, so I implemented my universal literacy project. (I was also a priest of the god of knowledge). The open goal of this project was to make sure that everyone could perform basic reading and math. The secret goal was to set up an institution that would teach the children loyalty to me and my ruling dynasty at a young age.
Among the other strange issues I faced was a strike by the elephant handlers union. By "elephant-handlers union" I mean a union of intelligent elephants who handled overland portage tasks (No I am not joking.) As a result of a divine geas I has to treat animals as I would treat people. When the elephants went on strike due to poor working conditions, I had to negotiate a contract for them to work . . . for more peanuts . . . and allow them to unionize. (Again I am not joking.)
I think in the end, the whole project cost me upwards of 40 million gp to create my little paradise of about 7,000 souls. I must admit that looking back on the whole affair it was a lot of fun.
With regard to your PCs project, I thing cost estimates and time estimates I have seen so far are too low. Unless there is a natural disaster that causes a refugee flow, you'll have a hard time building a population much past a couple of thousand souls in a few years. I used a LOT of magic (including a wall-size mirror of mental prowess and a spelljamming ship) to scour a continent and move 3,000 people in a short time and this still cost me a LOT of money. Once that initual influx was over all I ever got was a mid-sized annual flow of new citizens.
It also takes a lot of time to build an infrastructure (unless you can get ahold of a lyre of building). (Again at tremendous cost I hired genies to build my city quickly). Wooden buildings can be build moderately quickly assuming the wood supply holds out, but they aren't permanent. Good building stone is slow to work, expensive and hard to come by unless your happen to have a local quarry.
The hardest part of building a city is creating a sustainable economy. Unless you can find a cash crop, farming won't do it. Mining is messy and doesn't last forever. Whatever you use however requires you to be fortunate and have nearby markets (and hopefully a river for cheap transport) or it will cost a lot to transport. Regardless, it will take years before the city is self-sufficient (if it ever is).
However your group decides to do it, let me tell you city building IS fun but the DM does have to be on his toes. Think of it as Sim-city meets Warcraft.
Tzarevitch
