We're all simply accepting Dr. Soong's marketing is true about Data, that he never forgets anything. Just because Data says "I remember every fact I am exposed to, sir." doesn't mean he actually does. His various tricks with voice acting and long strings of data (like his verbal access codes) are impressive to us mere mortals, but for even modern computers they're not very impressive.
Data likely has a tiered storage system. (https://en.wikipedia.org/wiki/Hierarchical_storage_management) He obviously has a short term memory which he can purge data out of at will. The relationship program he deletes was most likely in the transient storage layer.
He'd have working memory, short term memory, and long term archives. (I always imagine when he tilts his head and says something like "working" or "searching" he's unpacking an archive). Remember, it's not just raw data size, it's the compressibility of that data we should be thinking about. Most days are the same, most facts are similar, and Data can use file de-duplication and file compression to archive long term memories in a way we simply can't as wet computers. This would allow him to "never forget any fact" while not necessarily "remembering everything." Some things just don't need to be remembered because it's exactly the same as something else.
Finally, Soong worked really hard to make his androids as much like humans as possible. Lore even had emotions. For Data, Dr. Soong intentionally dampened his emotional ability (although I'd dare say he's got some emotional undercurrent, even if he acts unemotional) to avoid the types of problems Lore caused. However, if we assume that Dr. Soong's success was because he tried to model humanoids, he likely also modeled Data's memory system on ours. It's likely he has a ton of storage, but like us, long term memory is more about reconstructing the memory from scattered remembered impressions. Data can supplement those with actual logs of actual spoken words, for example.
And it's possible that Data isn't even aware that he's actually forgetting plenty of things and only reconstructing memories or whatnot. Does C3PO actually use over 6 million forms of communication, or is that just his marketing introduction? How many times has C3PO told us that he knows 6M forms of communication... but that one is one he doesn't know, or he thinks it MIGHT be something else, or it's similar to one he knows. Isn't it possible C3PO just knows the nuts and bolts of communication and protocol and knows a few thousand of the most important languages, and handwaves the rest? Is he lying, or just telling us what Cybot Galactica's marketing department programmed him to do? Data's not lying, he's just saying that Soong told him about his memory.
Finally, we've seen at what speed and ability Data is able to access the Enterprise's computer to bring up mission data. I find it a bit unbelievable that Data hasn't thoroughly researched every mission in his quarters before his shift. He's got plenty of time available, and the show makes it clear that his work is his life. He's been seen working the night shift, etc. So why does he have to access the Ops computer so often to give Picard information about the mission? Supposition: he knows WHERE the data is in the computer, but didn't bother retaining it in his personal memory because it's accessible when necessary.
TL;DR: Just like Spock depending on everyone "knowing" that Vulcans Do Not Lie (despite them often lying in Enterprise, and "not completely telling the truth" in other properties) and Do Not Have Emotions (despite Vulcans showing off many emotions, and having more or less success at repressing them), I'd say that Data's "I don't forget anything" is nothing but marketing.
It's totally believable to us bags of mostly water that a walking, talking computer would have no emotions and have instantaneous, total recall. His various parlor tricks of voice acting and such would impress upon us his massive memory capabilities.
But just like Vulcans who can lie and have emotions, Data can forget details and shuffle memories into highly packed, somewhat lossy storage (like a JPEG vs a PNG). When he needs them, he can unpack them, reconstruct details with heuristics, and supplement his memory with the computer, all while maintaining that he never forgets anything.
