Will a 100GB disk with 1,000,000 files take longer than a 100GB disk with 100 files when running
That depends on the file system and the switches you use with fsck.
fsck Checks and Tries to Repair gives a pretty detailed explanation of what fsck does when invoked without switches.
Some of the checks take a constant amount of time (e.g., super block check), many of them depend on the number of inodes fsck has to process (e.g., link count checks), others on the file system's size (e.g., regular data block checks).
-c switch, fsck does not check the contents of regular files, so the size of the files is irrelevant. Even when checking for bad blocks, the execution time only increases with the file system's size. Which portion of the of the partition is occupied does not affect the execution time.1
The number of inodes of a file system is constant, i.e., decided upon at creation time. Each file's metadata is stored in one of such inodes. According to ext4, unused inodes are marked as such in ext4, but not in ext3. Thus, fsck's execution time increases with the file count in ext4, but is constant (and high) in ext3.
The following figure illustrates this:
Observe that the different file counts are represented by different colors. The graphs for ext3 with 2.1 million, 100 thousand and even zero files are identical. The graph for ext4 with 2.1M and 100k files respectively show a significant difference.
In contrast, execution time increases with the number of inodes with ext3, while unused inode do not impact execution time with ext4.
1 Verified empirically by running
fsck -c on an empty partition.