Let's see, 512x512 / 128 = 2^18 / 2^7 = 2^11 = 2^5 x 2^6 = 32x64 tiles for each town, and then you don't have room for any water, any tracks, or any industries.
As a generic setting for all types of play, it looks quite reasonable to me for 100 year city growth where you don't get stuck completely by expanding towns in 50 or so years.
There is one other possible reason not mentioned yet here so far, I think, which is using a NewGRF for town names. Some such NewGRFs have a limited number of unique names, and since OpenTTD doesn't generate towns with duplicate names, that would also limit the number of towns you can have.
The default name generators have enough names to avoid this limit.
I don't look much for OpenTTD youtube movies, as they don't tell me much new, and if they do, they take too long
Are you sure they just generated a random map, and not have something prepared beforehand?
It seems reasonable to assume that when you intend to show some feature in a video, you prepare for it, which thus might also mean they prepare a map beforehand, which doesn't limit them to the random map generator.