You are partly right that it's because of other Aiel siding with them, but that's not the only thing. Several factors contributed to the Shaido becoming such a problem.
- As you mentioned, many Aiel refused to accept what Rand revealed, and left their clans to fight with the Shaido while still in the Waste. These are referred to as the "Brotherless" Aiel.
- Many more of the Aiel simply walked away and refused to follow their clan leaders, and Rand, out of the Waste. They threw down their spears and just abandoned their people. The Shaido Aiel did not suffer these losses, because their leader proclamied the whole thing a lie.
- Once they were across the Dragonwall, Couladin allowed his Aiel to pillage the wetlanders and take their stuff while Rand tried to rein them in and prevent war. Over time, many of Rand's Aiel just abandoned him and went back into the Waste.
- Rand assigns his remaining Aiel to a number of important jobs, including scouting, policing conquered cities, etc. The Shaido, on the other hand, are primarily focused on one goal -- attacking wetlanders. This makes them seem far more dangerous.
- Eventually, we learn that the Shaido were being aided by Sammael (sort-of), which gave them an advantage over Rand.
It's important to note that the Shaido alone are not stronger than all of Rand's Aiel combined. By most estimates, Rand has between 400,000 and 500,000 Aiel following him at any given time, while the Shaido alone number maybe 160,000. But note that Rand has eleven clans of Aiel with him, meaning the Shaido's number is almost four times as much as any other single clan.