I haven't used Prolog at that scale myself, but I'll just add completely unsubstantiated hearsay from the ##Prolog IRC on FreeNode: Someone reported no problems using SWI Prolog for running queries on "59 million facts".
It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies.
Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages.
Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try...