The TLDR answer:

If you are using a flat structure(i.e. no directory inside bucket) to upload objects to the S3 bucket, then there you go that is the answer. I have worked with buckets that have 2M objects but in a flat structure taking almost 5x the time to upload an object of 1MB size file. The moment I created one directory structure the upload time drop drastically.

Since there isn't any resource available on the internet on how S3 works under the hood, it is going to be difficult to explain the primary reason for this. Even reaching out to the support also didn't help much.

So in short if you have a flat structure in S3 bucket, time to move to a folder based structure to solve the performance issue. 😎