Handling 4M files in a single filesystem is no problem for ext4, so long as the filesystem is formatted with enough inodes. It is no problem to even have 4M files in a single directory, if the filenames are not excessively large.
There are Lustre filesystems with 1.5-2B files, and 10-12M files in a single directory (which is about the directory limit until kernel 4.recent when the "large_dir" feature was added). That means you don't need to do anything special with the directory structure to handle the files, unless you might need to store many more files in the future, or if you have a regular turnover of files, where you might want to make "age" based directories and then delete them after some time.
Reasonable formatting options would be:
mke2fs -t ext4 -i 32768 -b 4096
-i 32768 = average file size is 32KB, to ensure enough inodes
-b 4096 = blocksize, to allow large directories
The default inode size is fine, unless you store a lot of xattrs on each file. If yes (use
getfattr -d -m- -ehex /path/to/existing/file to see what the average xattr size is), then use
-I to increase it. The core inode size is about 180 bytes these days, and the rest is available for fast xattrs.
If you put the filesystem on an LVM/DM device, then you can also resize it online to add more space/inodes if you need more in the future. What you can't easily change is the inode ratio or inode size.