Adding a "my messages (x)" link in the block template file
The module already contains a block that does something similar: "New message indication". You can use that block and alter the output if needed by overriding the theme_privatemsg_new_block() function.