I believe they do. In the current engine (which EUIV is partially based on), adding a significant number (like doubling the count) of tags does slow down the game. Because those tags still have relations, sliders and other things going on and flags must be calculated for them. When calculating claims on a region, the engine checks to see how many provs a nation has. It cannot tell if it has 0 claims without first checking each province anyway and each tag anyway.
Or at least that is what I am led to believe. It is one of the two issues facing MEIOU right now. People want more tags, but tags seem to be slowing things down (when the map is held constant).