Doubtless means without a doubt*, so it works as an adverb (in addition to being an adjective) even though it lacks the adverbial -ly ending. The -ly ending in the adverb doubtlessly is redundant and unnecessary.
Doubtlessly is not wrong, but it can, and maybe should (?) be replaced with the shorter alternative. It addition to doubtless, there is the adverbial phrase no doubt, and there is also the slightly longer undoubtedly, which is more emphatic.
These writers use doubtless as an adverb:
For younger fans, the impression of seeing a real-life prince will doubtless linger longer.
If you asked the men involved, they would doubtless point to greed as the primary catalyst in this transformation.
If he makes it to the run-off, he would doubtless find Mr Kuczynski an easier opponent than Mr Toledo.
If you want to emphasize your lack of doubt, you can use undoubtedly
I saw no wildlife, although they undoubtedly saw me.
The threats are undoubtedly hyperbole, but how many of our bosses would put up with them?
Global warming will undoubtedly lead to global warring over resources.
Having said that, you will find doubtlessly used often enough. It's not wrong, it's only redundant. When in doubt, try doubtless.