TanisFrey makes a good point, you don't need paperwork for your followers but there's also no need to just abandon them altogether. A buddy of mine used his followers very creatively, turning them into a spy network.
But your trade off, no followers = -1 level for cohort seems fair. The followers feat also looks good, but I would just modify the Leadership feat so you get either extra followers or a -1 level cohort. Don't let someone take both.
I am one of three players in my 3.5 game with the leadership feat. In fact in someways my character is most involved in her leadership score as I have a second feat, Dragon Cohort from the Draconomicon, granting her a second cohort.
As I wrote only half of my followers that I have done almost nothing with. The other half has notes of what role they play in the thespian group. I have notes on what level bards are actors, what level experts are the carpenter, seamstress, painter, blacksmith and their assistants. I have notes on the levels of the warriors and their fighter captain whom guard the caravan plus the few extras in the group. My non-combat Cohort is the playwright of the thespian group.
The rest of the followers I noted that they are 1st level commoners, experts, aristocrat and that they are spread across the region. This allows my to ask the DM the question, I do have any followers in this town that I can go ask questions of?
The other two players with the leadership feat are using their followers in other ways. One is a Prestige Paladin of Sune, a Baron of Corymar, his followers are his troops. His cohort is an evoker, his siege warfare expert. We are trying not to get into any border wars with his neighbors.
The other is a Bard, who is a retainer of the Baron, she used her followers to form a spy network with her cohort being it head.
Most of the time the followers are not involved in the character adventures. The cohorts are more involved. With how the game is going the Paladin player and myself do not have our PC's with the group right now. The Paladin is running his Barony and my PC is at his side. The baron sent his squire (6th level follower) with the group. My dragon cohort also feet it would be fun to follower the group.
So I am saying that there several way to run the followers in game. You are playing Kingmaker. The players have a kingdom to populate and run, their followers can do that in the background with a minimum of paperwork on their part. Followers do not need to be new settlers to the area, they can be existing residents who see the stability and safety that the new kingdom will give them, so they give their new master their support.