Welcome to CFC!
You haven't said whether you have Warlords & Beyond the Sword or just plain Civ 4, so these instructions include all of them, ignore those you haven't got. You haven't said what OS you have but hopefully the info here will allow you to find the folders even if they are in a slightly different place.
Try to follow this order when doing stuff:
Use Control panel to uninstall Beyond the Sword, then Warlords, then Civ4 if you can
Delete "...\documents and settings\<username>\my documents\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\my documents\my games\warlords" manually
Delete "...\documents and settings\<username>\my documents\my games\beyond the sword" manually
Delete "...\documents and settings\<username>\application data\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\application data\my games\warlords" manually
Delete "...\documents and settings\<username>\application data\my games\beyond the sword" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\warlords" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\beyond the sword" manually
(note: application data is a hidden directory so you need to configure windows explorer to show hidden files, also these directories in application data are sometimes removed by the uninstall routine)
Delete "...\Program Files\InstallShield Installation Information\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}" (Civ4)
Delete "...\Program Files\InstallShield Installation Information\{3E4B349F-10B5-4586-9D99-489A90A8B228}" (Warlords)
Delete "...\Program Files\InstallShield Installation Information\{32E4F0D2-C135-475E-A841-1D59A0D22989}" (BtS)
(note: InstallShield Installation Information is a hidden directory so you need to configure windows explorer to show hidden files).
