I think the main issue is how aggressive these nomads are. As has been mentioned, there have been huge groups of nomads through history that sustained very high numbers, such as Huns, Mongols, and even Vikings, however they were largely warlike or predatory groups. More peaceful nomads, such as the Roma or Celtic blacksmiths, were often much smaller in size.
Based on what you said they do for a living (herding, trading, raiding), and given that they have approximately 10 million people to live off of, I would say the biggest possible groups might a few hundred individuals. Again, this is dependent upon town size. If you have 10 huge cities with a million people each, it would be much more realistic to think that a group of 300 nomads wandering in would be tolerated. If you have some 500 settlements of 20,000 (which would be quite large for a medieval setting, though not impossible), a few hundred nomads is a much bigger concern. Besides the possible negative reactions of city-dwellers to any group large enough to be a relative 'hoard,' you have to consider the jobs/resources available. If you have thousands of small villages, a traveling blacksmith can support himself and perhaps a few family members on the work he finds, but there would certainly not be enough bent shovels and dull axes for even a dozen fellows. Large towns would afford more opportunities for work, however they might also require your nomads to stay longer. It is also far more difficult for 300 nomads to graze their animals on a few scattered grass patches than it is for just a handful.
Based on the situation you describe and the little bit I know of Bedouin tendencies, I would imagine your nomads live in extended family groups of twenty to thirty people. These groups are probably quite familiar with one another as they would frequent the same water holes and grazing lands, but generally would not travel together. In a group of 20-30, your nomads can herd a sizable number of animals, though not so many as to overburden the scarce desert resources. They are not an intimidating presence in the average village of 2-3,000 people, but have the numbers to launch small-scale raids on isolated farms or traders. While threatening to city-folk who wander beyond their walls, larger caravans, such as would be necessary for intercity trade, would be relatively safe, meaning kings/governments would not feel it necessary to move against the nomads. In a band of 30 people, with high birth/death rates, you probably have 6 or 7 kids and 23 or 24 adults. When they stop in a town, say half the tribe tends to the children and the livestock, the other half works odd jobs, that's only some 12 people, meaning that even small villages would likely have enough occasional work to keep the nomads employed, but not so much that the nomads could settle down for good. This would also explain their reluctance to go to more fertile lands or to the steppes as they do not have the man-power to claim territory there.
Based on this system, a large tribe could be 50 people, but I doubt it would last for long. You could get a roving city if the nomads decided to band together, but this would of necessity be a predatory system, similar to the Huns or Mongols. I should think the largest troupes of nomads would form only rarely, when two or more regular groups joined forces, probably in a large-scale raid, perhaps on bigger caravans, or in a case of war. Intertribal politics would be a major issue that you could explore or exploit, should the need arise.
In general, I wouldn't expect your nomad group to be larger than maybe 10% of the size of your average city, and even that is pushing it. A group that big has to be considered a threat and almost certainly must be predatory to remain nomadic. That said, what you consider a 'tribe' is also important. A band of 20 nomads could belong to a tribe of 100, if 'tribe' is taken to mean a loose affiliation.
