As described by a friend who went through this:
Since you lost the passport, you need to go to immigration department and apply for a special pass. The link lists the documents you need to bring:
- Passport number / copy of the lost passport / travel document;
- New Passport / Travel Document;
- Police report;
- Plane / bus / ferry ticket (depart within 7 days)
- Money (see below)
those are not mandatory but would be helpful:
- Any evidence of entry (land passes/tickets/list of passengers);
- Certificate from the Embassy;
- Copy of pass / previous document (if any);
You will only get the pass if your overstay is 14 days or less. Come early and expect to spend a few hours there, there's a line.
Money: it will cost you 100 ringgit for the pass. Since you overstayed, you'll have to pay additional 30 ringgit for each day (in 2015) you would overstay until you leave the country, so if you are already late for 4 days and your flight leaves in 2 days, you'd have to pay for 6 days. So in your case its 280 ringgit. Bring more money in case they raised the fine, or start collecting additional fees.
You will get an "overstay" stamp in your passport, and will be banned from reentering Malaysia for some small period (2 or 3 days per each day overstayed).
This will only work if your overstay is less than 15 days.