What it affects the most is the indexers, not only the URL rewrite index, which indeed has a glitch in CE, and disabling products does not remove them from the index. Also, price index, attribute index for layered navigation, search index, and flat article index. Incidentally, those grow about linear to product count * store view count, so you should consider deleting your unused stores as well.
Indexing performance also is affected by the number of combined products (bundle, configurable), number of categories, number of customer groups, and number of filterable product attributes.
It's not unusual for a full reindex to take several hours, so I'd definitely recommend optimizing it where possible. Also, partial reindex is affected, which means with fewer products, saving a product in the backend will be faster (if the indexers are configured as "update on save")