They didn't store anything themselves since they encoded the full state in the urls that were given out. So the link shortener was the only place where the "database", the urls, were being stored.
In other words, every shortened url is "using the url shortener as a database" in that sense. Taking a url with a long query parameter and using a url shortener to shorten it does not constitute "abusing a link shortener as a database."
It’s simply a normal use-case for a url shortener. A long url, usually because of some very large query parameter, which gets mapped to a short one.