Without his roe: i.e., looking very thin, like a fish which has dropped its roe [eggs]. Also, Romeo's name without the "roe" is "me-oh," as in "Oh woe is me, Oh!" In both parts of his pun, Mecutio is making fun of Romeo as the hopeless lover of Rosaline, because lovers were supposed to look thin and be full of woe.
Dried Herring
Image Source: Flickr