The built in automatic method that takes the least time to complete is almost always "Unwrap." For a simple mesh of 300,000+ polys, it took about 10 seconds. "Light map pack" took about 20 seconds, and "Smart UV Project" took longer than 1 minute.
For your mesh, I don't doubt that it will take longer, but it shouldn't be hours (I'd think). It may actually help speed up the process to mark some arbitrary seams. If you can, select two points, then choose Select -> Shortest Path. That will give you a contiguous line of edges that you can then mark as a seam. Mark a couple of seams lengthwise to split it into dorsal and ventral halves, then maybe even into quarters. Splitting things up this way, usually helps "Unwrap" work faster, but doesn't have any effect on any of the other methods.
Hope that helps!