We're in a similar position to you. We'll be coming out next year with a just-turned 8 year old who will have no Chinese at all, and is completely blue-eyed, blonde-haired white. When we come for a scouting visit in four weeks' time we'll be dropping by the various school options.
While I don't have experience of Taiwan, I do have the experience of taking a 5 and 2 year old to live in Laos. At that age adaption and acquisition of language is automatic, and the benefits of being a falang outweighed the disadvantages. Now in both our cases out children will be quite a bit older, and adaption slows as they age, though the speed at which they do it still far exceeds an adult.
How do I know this? Well, I taught English for Speakers of Other Languages in the UK for many years, and the children of the people I taught were leagues ahead of their parents in no time, so that you got the inevitable parents relying on their children for interpreting. This applied to even quite old children. In fact, at my older sons' school a Polish girl arrived at aged 14 speaking no English and went on to ace her A' Levels four years later.
That said, that was Polish and Eastern Europeans have an excellent attitude to education that puts British schoolchildren to shame. I've no doubt that the greater difference between English and Mandarin as opposed to a European language will slow the process. And acquiring written Chinese would be an uphill struggle starting so far behind their peers.
I'm in no position to advise you but wanted to let you know that I think it wouldn't be impossible, just pretty difficult, and you're risking your children's emotional well being to put them through, though with clear benefits to them in the end.
From our perspective, I would rather that our son went to a local school at least until high school, both because I know total immersion will be the quickest way for him learn Mandarin (our main reason for moving to Taiwan) and because I'd rather not that he became insulated in the expat bubble world. However, I know that that would entail a big risk to him and the last thing I want is for him to hate his life.
We're lucky in that we can afford to send him to TES, though it would be a significant proportion of our income, but that could well defeat our purpose. (I was reading someone's blog who'd been here 2/3 years and her children couldn't speak anything other than English - how is that possible?
) So in our trip we're hoping to have a look at one or two bilingual schools that may be a happy medium (and cheaper!) Not sure if such schools exist in Kaohsiung but that might be something worth checking out. That way the difference in cultural aspects of schooling wouldn't be so great either. I agree with other posters that this is potentially a source of greater harm than the language difference.
One thing you could do is start teaching them written Chinese at home, now, and also as much spoken Chinese as you can. There are a huge amount of free or fairly cheap resources out there and it could become an enjoyable parent/child bonding time too. I'm not sure what exists in children's Mandarin TV programming, but our son watches a lot of Japanese cartoons and can now pronounce a lot of Japanese, knowing roughly what he's saying from the subs. I think the thing is to maybe go for a trip and do your research. Be prepared to return if things don't work out. At that age a year's disrupted schooling isn't going to be life-changing. With a lot of preparation and care it may not be disastrous, and the struggle it will no doubt be worth it in the long run if you succeed.
I know I'm overstepping myself with this and bow to experienced forumers' superior knowledge, but also know that kids are very adaptable and resilient. Even in the case of an generally unhappy time, the experience of living for a year in a very different culture will benefit them for the rest of their lives.