Computing the exact volume of a polytope is known to be #P-hard by a result of Dyer and Frieze. See
here for a quick overview (and the reference).
polymake computes the (exact) volume by triangulating the polytope. This is implemented via the beneath-and-beyond method. The key factor in the running time is the size of the triangulation computed. For an estimation of the running time, e.g., see my paper "Beneath-and-beyond revisited", Algebra, geometry, and software systems, 1-21, Springer, Berlin, 2003. The problem is that there are polytopes which may look small (few vertices and few facets) but still every one of their triangulations is huge. In that sense you might just be unlucky. You can try to sort your vertices in a different way ("placing_triangulation" takes a permutation as an optional parameter), but this is not guaranteed to give you anything better.
Presumably, the best method to compute volumes approximately is Lovász, László and Vempala, Santosh: "Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm". J. Comput. System Sci. 72 (2006), no. 2, 392-417. However, I am not aware of an implementation available. In particular, polymake does not do that (as we are less interested in approximate results).
