Try changing the graphical settings. Run "Graphic mode setup" in the game folder and try switching between the options. I use 'openglnb'.

Blood can run slow because it's running in DOSBox, which emulates a whole second computer in software mode. As this is fairly heavy on your CPU, the better CPU you have, the better performance you will get.
The good news is that Blood has been around for a while and people have been trying to get it to work on many different computer setups.
If you are running Windows XP, you can actually run Blood natively to varying degrees of success. (see Build on XP: http://buildxp.deathmask.net/) This won't work if you are running Vista or W7.
If you have a recent CPU you might be able to turn on hardware virtualization in your BIOS. If you don't know if your CPU is capable of this, try running SecureAble: http://www.grc.com/securable.htm It should let you know if it can quickly. You can also just poke around in your BIOS and see if there is a section on virtualization. (reboot and hit F2 at boot time will probably get you there)
Note: I don't know if DOSBox actually takes advantage of hardware virtualization, but it may well help performance if it's turned on.

Would increasing the virtual memory that dosbox is allowed to run Blood help at all? If so how would one go about changing that?

How about some specs then go from their to diagnose a performance issue.

Hello! I am having similar problems!
I'm on an ASUS EEE PC, 1.6ghz atom processor, 1gb of RAM, Windows XP and an Intel 945 graphics chipset.
SHOGO and Conflict Freespace run smooth and fast but under DOS Box, Blood even on the lowest res with the detail down low stutters pretty badly.
I've tried changing to different graphics options but they don't seem to make a huge amount of difference.

Here are the specs:
Vista Home Premium
Intel Core 2 T7200 @ 2.00 GHz
2.00 GB
Nvidia 7900 GS

I too have problems with the frame rate being slightly choppy, but it's not enough to be more than a mere nuisance. The game is playable and it's not a hindrance at all, but I wouldn't mind fixing the problem.

I remember trying to run Duke Nukem under Linux on an EEE and running into very similar problems.
Something I meant to try but never got around to was installing DOS (maybe FreeDOS) directly on an SD card, booting from the SD card (by holding down ESC at boot, IIRC) and running the game natively in it's intended OS.
I believe the DOSbox overhead is just too much for the eeePC,
http://forum.eeeuser.com/viewtopic.php?id=7697

I didn't know that it DOSBOX would be so taxing; that actually is a surprise. I suppose I can close this now. I'm happy with the game even on the lowest settings because it's so damn fun I could care less as long as I get to play it.
I appreciate everyone's answers/suggestions.
Thank-you.

I'd have to say the OP's issue was not properly addressed, since his desktop cpu is nowhere near as slow as an atom.
totally different scenarios here.
OP is probably having an issue with the renderer, and using OpenGL might solve the problem.
Edit:
I'm not the first to mention this either, but OP never said if he tried using OpenGL.
Tip: change it manually in the config file, I've had problems with the gui.

Emulation in general eats up a lot of CPU resources.

Point being? Are you inferring that the OP's CPU is inadequate?
Before GOG released blood, I was running it on an athlon64x2, which is "slower" than a core 2.
OP just has something configured wrong. (Unless he's trying HD resolutions.)
Worst case scenario, he can install a CVS build and D-fend Reloaded for optimum performance.
http://www.si-gamer.net/gulikoza/
http://dfendreloaded.sourceforge.net/
640x480 is a decent compromise, while 800x600 is probably the best resolution to run, any higher and it's diminutive returns.

Entropy, I did set the graphic mode to OpenGL and that still did not fix the issue. But thank you for giving suggestions.