What do 总 and 不时 mean here together? 他说，当公司总经理从他身旁经过时，总会不时地赞美他“你扫的地真干净“。

It seems I have 总 ‘always‘ and 不时 ‘occasionally' or 'often' together.

Does the 总经理 always or occasionally laud said sweeper? Or is it 'on all occasions'??
You need to consider 总会 together:
ABC

be bound to; be inevitable; be sure to happen

总会 + 不时 = be sure to + often = he is bound to frequently.../he is sure to often...
ABC calls 总会, here, a:
Verb Phrase

Dòngcí Cízǔ 动词词组
This includes
(i) descriptive predicates that do not behave as stative verbs, e.g., ǎirán ‘amicable; amiable’, as well as
(ii) phrases and longer chunks containing a verb that are not fixed expressions, e.g., bǎiláibǎiqù ‘sway; waver’, áidào tiānhēi ‘bear up until nightfall’.