Spoiler:
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".
