Based on experience, the steps are (sorry if there's any mistakes):
1) Take time to go back to Malaysia. You need to go to Pejabat Agama Islam Daerah to send the form "Permohonan Kebenaran Berkahwin (Perempuan)". And also the form "Persetujuan Wali dan Wakalah Wali" if your wali couldn't perform the nikah for you in Japan thus naming somebody else to be your wali. You need copy (I forgot if you need certified copy or not) of the IC of yours, your wali, and two male witnesses. You need to go together with your wali and two male witnesses, because there all of you will sign the forms in front of the Penolong Pendaftar Nikah. So it's better if you call the Pejabat Agama Islam Daerah first to make appointment with the Penolong Pendaftar Nikah, and confirm what other documents you need to bring.
2) Then, go to Japan (I don't know if you can do it by mail or at other country). Bring the documents you got from Malaysia, to the Embassy of Malaysia in Japan. There, the embassy will give you "Certificate of No Impediment To The Marriage", and the translated version in Japanese. Probably your husband-to-be must bring his Koseki Touhon (Certificate of Family Register) and you may need other documents.
3) Go to the City Hall (Kuyakusho/Shiyakusho) of your husband-to-be's residence (or maybe other place that are easy for you two). There, you will submit the "Marriage Registration" (Kon-in Todoke) form. In the form, you need the stamp of your husband-to-be, and also two witnesses. You need to provide the Koseki Touhon of your husband-to-be, your passport (I forgot if they'll copy it for you), and the "Certificate of No Impediment to the Marriage" with its translation, that you get from the Embassy of Malaysia in Japan, (and maybe other document also, please confirm with the City Hall).
The City Hall may need some time to register your marriage and re-arrange the Koseki Touhon. So, in the meantime, you can ask them to provide you the "Certificate of Acceptance of Marriage Report" (Kon-in Todoke Jyuri Shoumeishou). This will be a temporary proof of your marriage (according to the Japanese civil law). You will need this certificate or the new Koseki Touhon for your akad nikah in the mosque/Islamic Center.
4) Then, you can arrange your akad nikah in the mosque/Islamic Center in Japan. Your husband-to-be may need to bring his Muslim Certificate, or he can sign a new one before the akad nikah.
5) You can register your marriage in Malaysia when the two of you stay for good in Malaysia. But anyhow, you may want to register it earlier when you visit Malaysia, because you said you may not stay in Malaysia. The documents needed are as in:
http://www.jawi.gov.my/my/prkahwinan/senarai-prosedur/pernikahan/dafta...You may already found the answer. Good luck and congratulations :)