Flight Crew Multiengine; Flight Crew Instrument; Flight Crew Air Transport Pilot (ATP)
Communication Breakdown; Fatigue
Conflict Ground Conflict; Critical
Flight Crew Took Evasive Action
Human Factors
On pushback from ZZZZ ramp; mechanic on the headset advised tow bar disconnected; bypass pin removed and said he was clearing to the left. He appeared on the left; showed the pin and waived us off and walked back towards the spot.  We finished after start checklist and called for taxi.  Ramp cleared us and I turned the taxi light on and started to push the power up (could have been worse had we taxied on 2 engines) as I cleared to the left.  Then a tug front left tire appeared from below the cockpit.  I jumped on the brakes and stopped the airplane and observed the mechanic running back to the tug.  It apparently had stalled and he could not get it moving at that point.  Mechanic got it running and it moved clear.  No contact was made and we departed for ZZZ.Cause - I was a little tired after a lengthy new hire IOE trip and do not recall looking for the tug moving away.  I relied on the wave off from the mechanic.  The potential for a disastrous collision was definitely there.Suggestions - I should look more intently for the tug to pull away and the mechanic should not be waving off with a tug under the aircraft.
Air carrier Captain reported nearly colliding with a tug that had stalled after they had cleared the crew for pushback at a foreign airport.  The Captain immediately 'jumped' on the brakes after seeing the tug was still there.