I missed the part in the description that your game is mostly video and based my first comment around the assumption that your images are very big. They are, but contribute only marginally to the file size. Still all your images could easily be compressed to less than an average of your already compressed videos.
Maybe highlight that fact with the video heavy content and put as first or second screenshot part of one of the videos as an anigif. It makes your game stick out, as such kind of video sequences are rare. And the first 2 screenshots appear when hovering over a game while browsing. Actually, you could also make the game capsule image be an anigif.
I know little about video game movie compression, as this would be tied in to how those videos were created. But I do know some bits about video compression in general. And something is off here. There are too many artifacts and the files are (still) too big for their quality. For "mp4" compression, I assume some variant of h264 was used and there are worlds in quality difference achieveable. For the x264 encoder you would need to adjust some values to fit your content and not blindly encode in a bitrate. That sounds like a hardware encoder or some other bit of software that is optimised for real time encoding. Which will give very bad results for encoding - but is real time and meant for streaming.
The videos are artificially created and continuous. It just should compress a lot better with higher quality.
I cannot tell how webm configurations would look like, but mp4 with x264, you would select something like preset veryslow, tune film and try out the quality setting from 20-35 and since the source was created and is continous, it should still look good at very small sizes.