Having looked at you map route through Malaysia, I would suggest that you would find the East coast nicer to ride that the West Coast.
The west coast carries most of the North south traffic, and whilst there some nice back roads, they tend to meander somewhat.
The east coast has a north south Main route 3 which is busy, but not as much as the west coast, also there coastal kampoon roads which run along the coast. also the home stays(BB) are cheaper and plenty of them along the east coast.
The beaches on the East coast are great, long sweeping and sandy. also it is easy to enter Thailand there, and less chance of being robbed by the Bandits, which no one will tell you about that hang out on the west coast route in Southern Thailand:-)
Here is a route through Malaysia which I posted for another couple a few weeks ago.
If you fly to Singapore, leave Singapore via the Causeway into Johor Bahru, nothing worth looking at there, cycle East to Kota Tinggi, stay there or cycle inland up into the hills to the Waterfalls at Lombang hotel is expensive or spend 2 nights at Kota Tinggi and have a day ride out to there. Leave Kota Tinggi cycle up the East coast of Malaysia, when you get to Mersing, take a few days out on Pulau Tioman, great Diving place, and you can arrange a package in Mersing then travel out either on the ferry or speed boat.
From Mersing, carry on along the coastal road, to Pekan, Not much to see there, but a few hotels which are cheap, but act as brothels at night so can be a little noisy from the sound of magical movements. Then to Kuantan here you could leave your bikes and catch the express bus to Kuala Lumpur for a few days.
Back on the road leave Kuantan, and head for Kuala Terengganu, here you can arrange diving packages for there for Pulau Redang you are really into Home stay accommodation now though the small towns have small hotels, most act a brothels in the evenings, but don’t let that put you off.
Leave Kuala Terengganu , once over the bridge there is a coastal Kampong road, take this and follow to Kota Bharu.
Kota Bharu is the border town with Thailand, not much there to excite.
Leave there and head for Sungai Golok, Cross over into Thailand, then head for Narathiwat there are Coastal roads to use, but some have a habit of curling back on themselves , thus you end up doing more miles that you want in the heat of the day.
. And presumably you will not be racing, which makes it an entirely different proposition to MBs trip.
.
