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][1] that also works for compact sets only, due to Henrion/Lasserre/Savognan.


  [1]: http://homepages.laas.fr/henrion/Papers/volume.pdf