You already got good suggestions on how to handle DNA contamination in protein preparations.
Let me point out briefly that you haven't demonstrated yet that your contamination is DNA.
I had the same observation when purifying UvsX. A very persistent and strong contamination in all my preps at ~500kb. To test weather it was DNA or RNA I boiled the protein 30 minutes and incubated it with DNAase and RNAse and result was the same. I concluded it was neither RNA nor DNA and continued as if nothing had happened.
This publication is reporting the same observation:
Formosa and Alberts (1986) "Purification and characterization of the T4 bacteriophage uvsX protein." J Biol Chem. 1986 May 5;261(13):6107-18.
If you ever find out what it is that runs like 500kb DNA on Agarose, please let me know.