What it affects the most are 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 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 to optimize it where possible. Also partial reindex is affected, that means with less products, saving a product in the backend will be faster (if the indexers are configured as "update on save")