Tim's map2map... map converter should work to convert the basics of it. You will more than likely need to go in and do some editing once it's converted, but the basic geomitry should be there.
My best guess is that Tim's map2map only converts plain BUILD maps to Quake maps. Blood map format is slightly different (encrypted actually). I think you'll have to first decrypt the map using blud2b, a tool Tim and I coded a while ago for the ReBUILD project, and available on our development site: http://blood.sourceforge.net/snapshots.php -> ReBUILD files -> Win32 binaries
Yes, and after you do that you will need a Quake map editor.
My pick is BSP, this is the editor I use for Transfusion.
But you can use any editor that comes to your mind.
Go and see Developer's Corner on our site. You will find the things you need there.
If I convert all the maps to quake format will they still work with a quake to half-life converter or is there something in them that will not alow it?