Can I use 'Tie::File' to generate the Hash (which makes this scalable to work with large files and small memory), should I work in memory, or is there some other Perl feature which will make this so easy that I will be embarrased that I asked the question.

Nope, from perldoc mod://Tie::File

NAME
    Tie::File - Access the lines of a disk file via a Perl array
[download]

You should work in memory if memory is enough. Otherwise if usage is large, go the tie way. Of course find a suitable module and not the one you mentioned. How 'bout DB_File for example?