Could I read it in a line at a time, look for the appropriate start/stop tags and parse it that way?

Alternatively, if your database dump is just a sequence of one kind of element, this should also work:

open(XML, "<", ...);
{
  local($/) = '</record>';
  while (<XML>) { ...process one <record> element... }
}
[download]

With regard to why your experiment on the 400M record table is taking so long... are you grabbing 1M records at a time by using a LIMIT clause (i.e. LIMIT n, 1000000)? If you have any index on that table (say on column colX), adding ORDER BY colX should help speed things along.