You are right that they have no way of looking up whether or not you left. For all they know, they could at this point assume that you are already back in the U.S. However, right now you are illegal and therefore you being here is a huge risk (ie., what if a cop pulled you over and was super diligent and wanted to check your status, etc.). That being said, you could get married on this trip to Canada, but you are here illegally, so you are running a large risk of major red flags on any application for PR down the road if it is found out that you were overstaying. And of course, there is that nasty consequence of getting sent back to the U.S. without authorization to return to Canada, that nobody wants to go through, especially when you have a loved one here in Canada.
I would strongly recommend this. Go home to the U.S. for now. At least it will give you time to think without risking being caught. Maybe take some time and plan out your wedding. It only has to be temporary. Then, when you are married, apply for PR outland. You are allowed to be in Canada while your outland app is processing, but when you do come to Canada after you are married, be sure to stop in at immigration with your marriage certificate, the receipts of fees for outland PR app, and your girlfriend (then wife). Ask for a visitor visa to stay in Canada, with the receipts as proof that you are going to be applying for PR. But you need to do all this after you are married. Right now, you need to go home.
Also, as a side note, if you are planning a wedding, I would strongly consider getting married in the U.S., depending on what state you are from, because in Ontario it takes at least 10 weeks to get a marriage certificate after your wedding.