Here is an algorithm: partition $\mathbb{R}^n$ into cubes of side $1/k.$ For each cube $C_i$, use your favorite quantifier elimination algorithm to check whether the set $S$ intersects it. Then, your bound is the number of cubes $S$ intersects divided by $k^n,$ which is obviously rational, and just as obviously converges to the volume of $S$ from above. You may argue that your set $S$ is not known to be bounded, so on $k$-th step make your cubes fill a cube of side $k.$ Granted, the algorithm will be rather slow, but given that even computing the volume of a polytope (that is, a semi-algebraic set where the inequalities are linear) is known to be hard, no really quick algorithm is likely...

Here is an algorithm: partition $\mathbb{R}^n$ into cubes of side $1/k.$ For each cube $C_i$, use your favorite quantifier elimination algorithm to check whether the set $S$ intersects it. Then, your bound is the number of cubes $S$ intersects divided by $k^n,$ which is obviously rational, and just as obviously converges to the volume of $S$ from above. You may argue that your set $S$ is not known to be bounded, so on $k$-th step make your cubes fill a cube of side $k.$ Granted, the algorithm will be rather slow, but given that even computing the volume of a polytope (that is, a semi-algebraic set where the inequalities are linear) is known to be hard, no really quick algorithm is likely...

UPDATE As the OP points out in the comment, the method as described only works for compact semi-algebraic sets (at least in so far as requiring upper bounds). There is a better (as in, theoretically faster) method that also works for compact sets only, due to Henrion/Lasserre/Savognan.