The canonical order to do things is to first write the documentation, then from the documentation write the tests, then write code until the tests pass. Of course, in practice that doesn't happen because your design evolves as you write the code and so you need to add/remove/change tests.
Your situation is slightly different in that you already have code, but I would suggest that you should first document what you've written do far. Documentation should include, for each method:
- the calling convention (eg named parameters vs an ordinary list);
- which parameters are required and which are optional;
- any restrictions on the values passed;
- the return values;
- how and in what circumstances the methods should fail;
- any gotchas and corner-cases
Then write tests which check that your methods do indeed do what you expect them to do. Be aggressive in your testing, ensuring that you perform some tests with deliberately pathological data - for instance, if your documentation says "this method will die if the username is invalid" then check the situations where no username is passed (ie it's undef), where an empty username is passed (the empty string, '') and where a username like 'snafflegarb' or something equally silly is passed; if you have a method that expects a numeric argument, call it with argument 'pineapple', and with a reference, and with outrageously small numbers, stupidly big numbers, negative numbers ... If you're feeling particularly nasty, try testing with Math::Big* objects.
If you are implementing complex algorithms, you should in theory derive the results to test your code's correctness in some other way, but if you are confident that your results are correct, then I'd say it's OK to cheat and to use the module to generate its test results, provided that you throw in a couple of the simpler results calculated by hand yourself. Using the module to generate results which you then hard-code into the test suite is still useful, as it provides a check in the future to make sure you haven't inadvertently broken the algorithm in the next release.