The flashbacks show Broly wreaking havoc as far back as his teens, and he's the same age as Goku, so yes, it would appear he's been at it since at least that far back. It lines up perfectly with everything being present tense rather than past tense as you originally claimed. The galaxy can't be presently under attack if it's already been destroyed. I'm not denying Broly potentially has the power to knock out a galaxy, but he definitely didn't do it all at once like you're suggesting, because the flashbacks contradict this notion. Either he's already destroyed the galaxy or he hasn't, it cannot be both.
However, I am willing to admit that even the movie itself can be somewhat inconsistent with its idea of what exactly is going on/happened, after reading some off-site posts on the matter again. I'll just quote that post since it's better than what I could have said:
from Herms: 'So...it seems a little inconsistent. The narrator at the start just describes the Southern Galaxy as having "fallen under Super Saiyan attack". But later, Goku refers to Broli as having "destroyed" the Southern Galaxy, and Kaio at the start says "at this rate even my Northern Galaxy will be destroyed", implying the Southern Galaxy has been destroyed, or will be destroyed soon. Then when Paragus outlines his plan for universal domination, he says his empire would include the North, East, and West Galaxies...but conspicuously fails to mention the South Galaxy, implying it's not there to be ruled any more.
On the other hand, Paragus describes the Legendary Super Saiyan as "wreaking havoc all over an area of the Southern Galaxy", while Kaio tells Goku that the Legendary Super Saiyan has "already finished tearing up the Southern Galaxy". Most importantly, after telling Goku this, Kaio then instructs him to "go check the Southern Galaxy". At which point Goku teleports to a planet filled with ruins. So even if the Southern Galaxy has been "destroyed" in some sense, at least part of it is still there.
On that note, after Goku thinks to himself that Broli is the one who "destroyed" the Southern Galaxy, he shortly thereafter semi-repeats himself, saying that Broli is the Super Saiyan who "ran riot through" the Southern Galaxy. So it seems like all this makes the most sense if we treat "destroy" in this context as meaning that Broli attacked/laid waste/etc the Southern Galaxy. That is, he just went from planet to planet destroying the civilizations there, leaving ruined planets like the one Goku visits for a bit. The only thing that seems to indicate that he literally wiped it out completely is the opening shot of the spiral galaxy thingy dissolving into blackness, but this doesn't jibe too well with what we see/are told throughout the rest of the movie.
There's no line flat-out saying that New Planet Vegeta is in the Southern Galaxy. But Paragus at one point says that his true plan is to set up his base on "Earth, in the Northern Galaxy", implying that New Planet Vegeta is somewhere outside the Nouthern Galaxy. And after Paragus tells Vegeta that the Legendary Super Saiyan is "wrecking havoc" through that portion of the Southern Galaxy, he adds that "at his pace, even the New Planet Vegeta that we worked to establish will fall to the Legendary Super Saiyan…" Which could be taken to mean that New Planet Vegeta is also in the Southern Galaxy. Or it could just mean that Paragus is (pretending to be) concerned that once the Legendary Super Saiyan is finished with the Southern Galaxy, he'll move on to wherever New Planet Vegeta is, just as Kaio is concerned that his own Northern Galaxy is going to come under attack next. Anyway, I guess it ultimately doesn't matter too much one way or the other in regards to the big question at hand, since there's still that one ruined planet Goku visits which is definitely supposed to be in the Southern Galaxy. So we know there's actually at least a planet or two left there, whether or not New Planet Vegeta is one of them.
Also, a bit more on what the movie means by "destroy": it's said that Broli "attacked" Planet Shamo, after which its inhabitants were moved to New Planet Vegeta. But Planet Shamo is clearly still physically there, since we see Broli actually blow it up midway through the movie. This seems consistent with the idea that Broli went around attacking planets by destroying the cities/civilizations on them, rather than blowing them up Freeza-style. This is still consistent with Paragus omitting the Southern Galaxy from his list of stuff his big fancy empire will include; even if the Southern Galaxy is still around, it's now basically uninhabited (a ghost galaxy!), so there's not really anything to "rule".'
