The closest thing I know of to this creature, is the mythological Peng, a fish-bird hybrid from ancient Chinese folklore. Technically, it is either a bird that can transform into a fish, or vice versa.
I am not aware of any explanations in the anime or in the light novels for this creature, but I suggest that it was included to add to the fantastical atmosphere of the anime, add another magical creature to the repetoire, as well as being something fun and exciting for the viewers to watch during the credit sequences!
Nevertheless, the Peng is an appropriate creature to use as a model, since its flight was associated with being uplifted by 'righteousness' and 'virtue', and for a long time stood as a metaphor for 'broadening one's mind' or 'expanding one's horizons'. This is a very apt theme for Outbreak Company, which is all about 'breaking' through to the other side, and expanding into new ground, both physically and mentally. Both Kano and Myucel must grow and broaden their minds and experiences, and so the Peng is an excellent metaphor for them!