Once you've logged into facebook from the device, they likely created a device fingerprint for your device: https://en.wikipedia.org/wiki/Device_fingerprint . This would allow them to identify you even without a cookie or ad id to correlate against.
Fingerprinting across devices is possible too, using things like behavioral analytics, network traffic, timing, third-party data sources etc.
The third party data sources is the easy one. Log into service A on your computer and service A on your phone. Service A fingerprints both and sells the data to service B. Now service B knows how to correlate your behavior between devices even though you never logged in.
I’m sure you’ve logged in something on both your phone and computer. It doesn’t have to be Facebook.
