To delete 4 millions rows, it takes something like 10-12 hours. I assume that it is not normal :-). The server we have has 2 processors and 2GB of ram.
I have never had to deal with that many rows, but have had very bad performance in badly designed databases (5 hours to delete and insert 5000 rows on a low powered machine).
One of the killers when deleting is constraints. You could try disabling the constraints as you insert your data, then re-enabling them. If it is a "read-only" database you might not need them at all.
You might also want to look at your indexes. Foreign keys are not automatically indexed in Oracle: doing so can improve performance amazingly.
Finally, SQL*Trace and TKPROF is very useful in analysing performance problems.
See the Oracle manual on 'Designing and Tuning for Performance'. On-line version available at
http://technet.oracle.com/docs/products/oracle8i/doc_library/817_doc/server.817/a76992/toc.htm (you will need to register, but registration is free).
Hope that helps
Les