Haven't tried cpan2deb but cpan2rpm does not work with many CPAN modules and also it doesn't deal with dependencies the way CPAN does. So I guess they aren't as magical as you think.
Sure they are, why complicate things?
simple way, first build 500 perl modules and all required dependencies, and then make an rpm -- there you go
build it the way the debian release managers build it, one module at a time, until you have a chain of dependencies
It doesn't get more magical than this
In reply to Re^6: Finding Module Versions - How Would You Do It?
by Anonymous Monk