Since the rules don't say anything one way or the other, this is best sorted out between you and the player. You might want to take the following into account:
1. Rules restrictions. By the rules, a paladin can only have followers who are lawful good. This means that he cannot attract followers who are barbarians, bards or druids. Of course, you can always apply rule 0 as a DM.
2. Balance issues. Balance issues generally do not arise because followers are very low-level compared to the PC. However, if the PC does something that you don't really like, e.g. he recruits nothing but clerics and has them act as a scroll-creation factory, you can come up with creative consequences, e.g. his followers recompensed the full cost of creating the scrolls, they do not like what they are doing and desert, or a group of evil characters hear of his scroll stockpile and raid it.
3. Flavor issues. You don't have to agree if it doesn't feel right for your world. If a cleric of another faith would not follow him, you are within your rights to say no. If there just aren't that many low-level clerics who have heard of him, not all of his followers will be clerics.
4. What is fun? If his followers will not adversely affect the game, there is no harm in giving the player what he wants. Attracting a specific follower (or type of followers) could be the springboard for adventures or the reward for having helped certain organizations or individuals. Perhaps a cleric of Mystra shows up because the PC is working towards a goal that she supports, or because he has saved her in the past. Individual followers may also have their own agendas. Why would a low-level cleric of Sune decide to work for a paladin of Torm? Perhaps she is smitten by his good looks, but might she have some other motive?
At the end of the day, remember that taking the Leadership feat ought to be an advantage instead of a liability to the PC. After all, he has given up another feat to take it.