Overseas colonial empire doesn't necessarily mean they have to go to the New World, no? After all, Italy, Germany, Belgium, Austria-Hungary, and Japan only had territories in Africa and Asia and we call them colonial empires.
Han Chinese people had been visiting and living on Taiwan since the Song dynasty, so that could've been the beginnings of a colonial empire had they pursued further, more active ventures overseas. The main thing is that there needs to be some large incentive for the Song to formally back those ventures in a fashion reminiscent of the European colonial empires (religion, prestige, and/or money a.k.a. God, glory, gold) and not commit to the reconquest of the northern territories held by the Jurchen/Mongols. Religious conquest wasn't really ever a motivation for the Song, reconquering the north was always going to be the more prestigious choice, so it would've had to have been financially enticing (which colonial ventures tend to not be immediately unless there's literal mountains of gold/silver). And it would've needed to have been more profitable than just trading for the goods and not spending the time, effort, manpower, and financial costs of invasion.
And even if the above applied, if the Chinese suddenly stop caring for overseas ventures or are otherwise occupied (invasion from the north), then the colonies might just break off and become distinct in their own right. Chinese emigrants have been traveling, trading, and settling in SE Asia since at least the 9th century, so the changes might not be that significant. Though some interesting developments could occur, like the Kongsi Republics in Borneo coalescing earlier (since Kongsis were around in China since the Song dynasty and having a republican colonial government managing lucrative financial operations far away from the central government gaining autonomy/chafing under overseas rule and breaking away isn't necessarily dependent on technology) or more significant financial and military ties between SE Asia and China.