Fast bowler Malinga and off-spinner Muralitharan grabbed four wickets each as Bangladesh, sent in to bat at the P Saravanamuttu stadium, were dismissed in the first over after lunch off 25.2 overs.
Sri Lanka took a first innings lead of three runs by tea as they went into the break on 65-1 with Malinda Warnapura unbeaten on 36 and Kumar Sangakkara on nine.
Left-hander Michael Vandort was the batsman out, bowled by Mashrafe Mortaza for 14.
Bangladesh, thrashed by an innings and 234 runs in last week's first Test, fell below their previous lowest total of 86, also against Sri Lanka in 2005.
Malinga, 23, whose distinctive slinging action makes him a dangerous foe, created havoc in the rival ranks by scalping the first four wickets in a hostile opening spell.
The tourists were reduced to 22-4 within the first hour, before Muralitharan (4-14) and third seamer Dilhara Fernando (2-16) polished off the rest of the batting.
Muralitharan moved his career tally to 687 wickets, leaving him just 21 short of equalling retired Australian spinner Shane Warne's world record haul of 708.
Bangladesh, who were bowled out for 89 on the first day of the previous Test, once again found the formidable Sri Lankan attack too hot to handle.
Malinga trapped Shahriar Nafees with his fourth delivery and then had the other opener, Javed Omar, caught behind by wicket-keeper Prasanna Jayawardene three overs later.
The tourists slipped further as Malinga removed former captain Habibul Bashar and current skipper Mohammad Ashraful in four deliveries of his fifth over.
Bashar made five when he hung his bat out to an outswinger and was snapped up at second slip by Sri Lankan captain Mahela Jayawardene.
Ashraful fell to the last ball of the over as he flicked hard, but only to see Malinda Warnapura take a blinding catch in front of square leg.
Debutant all-rounder Mehrab Hossain lasted only 15 deliveries before he was bowled by Fernando after punching the previous delivery for a four.
Muralitharan, who came on in the 16th over, was hit for two boundaries by young Mushfiqur Rahim before the prolific off-spinner had him caught behind for nine.
Muralitharan had Mohammad Rafique caught in the deep before ending Rajin Saleh's defiant knock of 21 just before lunch.
Sri Lanka retained the team that won the first Test at the Sinhalese Sports Club last week.
Bangladesh made three changes, bringing in Mehrab, seamer Mohammad Sharif and 18-year-old wicket-keeper Rahim.
The trio replaced Khaled Mashud, Shakib-Al Hasan and Abdur Razzak.
Brief Scores (at tea, D-1):
Bangladesh Ist innings 62 all out (Rajin Saleh 21; Murali 4 for 14, Malinga 4 for 25, Fernando 2 for 16) Vs Sri Lanka Ist innings 65 for 1 (Warnapura 36 n o, Michael Vandort 14; Mortaza 1 for 24).