The reduction mostly came from non-permanent residents, especially international students and temporary workers. Their numbers fell faster than new arrivals.
Canada’s job growth is closely tied to immigration. Even if the overall population shrinks slightly, for exmaple when temporary residents leave, the labour force can still grow because new permanent residents and workers enter the job market.
These new entrants create demand for jobs, so businesses hire to accommodate both them and the existing workforce. This is why Canada can add more jobs per month than the US. That includes during periods of slow or slightly negative population growth.