There is a very clean and algorithmic way to do this. I will assume that the boundary of your polyhedron $P$ is a polyhedral surface. The first thing to do is to figure out orientation of the faces of $P$, i.e., correct cyclic ordering of their vertices. This has to be done in such a manner that if two faces meet along an edge, then this edge is assigned opposite orientations by the faces. For instance, if you have faces $ABCDE, DEFG$, sharing the edge $DE$, then you would have to reorient the face $DEFG$: Use the orientation $GFED$ instead. This is a purely combinatorial procedure which should not be too hard.
Next, I assume (for simplicity) that your polyhedron lies in the upper half-space $z>0$ (otherwise, replace $P$ by its translate). For each face $\Phi=[A_1A_2...,A_m]$ of $P$ consider its projection $\Phi'$ to the $xy$-plane and determine if the projection has the counter-clockwise cyclic ordering or not. If it does, mark $\Phi$ with $+$, if not, mark it with $-$. (Projection is done by simply recording $xy$-coordinates of the vertices of $\Phi$.) This part would be easy for a human, but there is also an algorithm for it which I can explain. Call this sign $sign(\Phi)$.
After this marking is done, for each face $\Phi$ of $P$ consider the convex solid $S_\Phi$ which lies directly underneath $P$ and above the $xy$-plane. Compute its volume, call it $v(\Phi)$:
$$
v(\Phi)=\int_{\Phi'} zdxdy
$$
where $z=ax+ by+c$ is the linear equation which defines the face $\Phi$.
Lastly,
$$
vol(P)=\left|\sum_{\Phi} \operatorname{sign}(\Phi) v(\Phi)\right|
$$
is the volume of your polyhedron $P$.
Edit. Here is a slightly more efficient solution assuming that each face $\Phi$ of $P$ is a triangle. First, you have to orient faces of $P$ as above.
For each face $\Phi=ABC$ of $P$ define the determinant
$$
d(\Phi)=\det(A, B, C)
$$
where vectors $A, B, C$ are columns of the 3-by-3 matrix whose determinant we are computing. Then
$$
vol(P)=\left|\sum_{\Phi} d(\Phi)/6\right|.
$$
