The GC has to check and find out which objects can be collected. My question is whether having too many objects to be checked can cause a GC overhead or somehow the GC is smart enough to avoid having to iterate through all the objects to find out which one is not referenced anymore?
Yes, it does matter to the mark-and-sweep collector how many objects you have. As to the size of those objects, that could matter too: a compacting collector would have more work to do if it needed to compact 10GB worth of stuff rather than 10MB of stuff.
Having said this, modern garbage collectors are extremely sophisticated (they operate on multiple heaps, do things in the background, can use multiple cores etc). They are also highly configurable. Furthermore, a typical JVM comes equipped with multiple garbage collectors.
It is therefore hard to give meaningful, precise answers to general questions like this.