How to reify Prolog's backtracking state to perform the same task as "lazy seq" from Clojure?

Prolog is a very reifiable language. Just turn your code into data:

qsort_gen(Lin, G) :- 
    % G is the initial generator state for Lin's quicksorting
    G = qsort_inner([Lin]).

    %    This_State                   Next_Elt      Next_State
next( qsort_inner([[], X    | WorkRest]), X, qsort_inner(WorkRest) ).
next( qsort_inner([[Piv|Ns] | WorkRest]), X, G ) :-
    pick_smaller(  Piv, Ns, SMs),
    pick_notsmaller(Piv, Ns, NSMs),
    next( qsort_inner([SMs, Piv, NSMs | WorkRest]), X, G).

pick_smaller(  Pivot, Ins, Outs) :- include( @>(Pivot), Ins, Outs).
pick_notsmaller(Pivot, Ins, Outs) :- exclude( @>(Pivot), Ins, Outs).

That's all.

15 ?- qsort_gen([3,2,5,1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[], 2, [], 3, [5, 9, 4|...]]),
X2 = 2,
G3 = qsort_inner([[], 3, [5, 9, 4, 8]]),
X3 = 3,
G4 = qsort_inner([[5, 9, 4, 8]]).

16 ?- qsort_gen([1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[9, 4, 8]]),
X2 = 4,
G3 = qsort_inner([[8], 9, []]),
X3 = 8,
G4 = qsort_inner([[], 9, []]).

17 ?- qsort_gen([1,9,4], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4]]),
X = 1,
G2 = qsort_inner([[9, 4]]),
X2 = 4,
G3 = qsort_inner([[], 9, []]),
X3 = 9,
G4 = qsort_inner([[]]).

For easier interfacing, we can use take/4:

take( 0, Next, Z-Z, Next):- !.
take( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

Then,

19 ?- qsort_gen([3,2,5,1,9,4,8], G), take(6, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8].

20 ?- qsort_gen([3,2,5,1,9,4,8], G), take(7, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8, 9].

21 ?- qsort_gen([3,2,5,1,9,4,8], G), take(10, G, L-[], _).
false.

take/4 obviously needs tweaking to close the output list gracefully when next/3 fails. It was written with the infinite lists in mind, originally. This is left as an exercise for a keen explorer.

This isn't standardized, but a number of Prologs nowadays provide facilities to maintain and manipulate multiple independent backtrackable states, often known as engines.

For example, using the corresponding primitives in ECLiPSe, you might write

init(Vars, Goal, Engine) :-
    engine_create(Engine, []),
    engine_resume(Engine, (true;Goal,yield(Vars,Cont),Cont), true).

more(Engine, Vars) :-
    engine_resume(Engine, fail, yielded(Vars)).

and use that as follows (with qsort/2 as defined by you)

?- init(X, qsort(X,[3,2,1]), Eng),
   more(Eng, X1),
   more(Eng, X2),
   more(Eng, X3).

X = X
Eng = $&(engine,"9wwqv3")
X1 = 1
X2 = 2
X3 = 3
Yes (0.00s cpu)

Here, the variable Eng is bound to an opaque engine-handle. This engine executes a nondeterministic goal that yields a new solution to the caller every time it is resumed and instructed to backtrack.