航空会社を変更されては

台湾に寄らなくてもよいなら、MHのホーチミン往復でクアラルンプールにストップオーバーすればよいのでは。
VNでもよいです。

SQでもSINにストップオーバーして、陸路クアラルンプールと言う手もあります。
SIN-KUL間だとJLとかが一部現地の代理店で格安航空券販売しています。