Assuming your income came with T4 slips, copies were sent to the government by your employers. (I believe you can ask for copies from Revenue Canada if you have lost yours.) This makes it possible for the government to estimate your taxes owed. They are likely to overestimate, since they won't know if you have deductions like tuition or medical expenses.
Your accountant can do a back-of-the-envelope calculation if you provide T4s or estimates of income, but does not have access to your T4s. The "tax tables" by which employers work out what to withhold for income tax produce refunds for most taxpayers (though not for most tax payers with more than one employer in a year) so it's also possible your accountant is just making an educated guess about whether you owe or not for a given year.
There is also a slim chance that you signed something for your accountant, who has used that to request your T4s and do a first pass of the taxes for the missing years. This still wouldn't answer the question of whether you owed or not unless you have also answered questions about possible deductions during that time.
Also keep in mind that the important question is not "did you have some taxes to pay" but "did you have more taxes to pay than were with-held from you at source?" This second meaning is what "you owe the government money" refers to, and it's very important. If sufficient taxes were withheld every year you have a paperwork mess to clean up. If not (common with multiple employers) you risk fines, interest, penalties, and even jail time. A lawyer is a better choice than an accountant in this scenario, unless you made very little money indeed.
Example of back-of-the-envelope work: a certain amount of your income is tax free. This is your "basic personal exemption" etc. Say that is $10,000 (it's actually a little more at the moment, but this keeps the math easy.) You pay taxes only on the amount of income above that amount. If you work for $1000/mo, the employer knows you're only paying tax on $2000, so they withhold just a few hundred dollars for income tax all year, say $20/mo. If at the same time you work another $1000/mo job, that employer may use the same logic, leaving you needing to send in the taxes on $10,000 when you do your taxes the next spring. But let's say you made $3000 a month for a while - they would take off as though you would owe taxes on $26,000. Then after just 3 months you leave that job and don't get another all year. You should have no tax to pay (since you only earned $9000 all year), but tax was sent in for you. In that case, you're owed money and interest. An accountant, who has all the rates, exemptions and whatnot easily to hand, as well as being able to calculate what your employers should have sent in, can give you a reasonable estimate in this way.