I've used CGAL's AABB tree and the Polyhedron data structure, to do something similar to what you just asked. But I had to do the actual cutting i.e. creating new vertices, adding new edges etc, were all figured out by me (or my teammates). And the CGAL library came in very handy for doing this.
The basic method was to use the AABB tree to figure out all the intersections between the line (or set of lines, in case of a polyline) and the mesh. You'll be able to get the intersections in a specific order from CGAL. Then you walk along them one after another, adding the new edges and vertices. Normally you don't have to add new vertices except at the start and end points.
The CGAL Polyhedron API supports dividing polygons along edges, which you can use as you walk along the result set. Internally, it uses a half edge data structure, which supports these operations from the get go.