Basically a programing language is whatever you define as a programing language. I don't think there is any standard definition of what it is.
So Perl is certainly a programing language. What you friend might be refering to is that some, amongst which some prominent (ex-)members of the Perl community, have problems with the fact that there is no formal definition of Perl: the language is defined as "what the perl interpreter can run". Which means that there is no single document describing exactly and completely the language, and (more annoyingly) that the language can (and does) change with each new version. This is seen as heresy by "formal computer scientist". It violates all the supposedly good rules of software design.
My take is that this is both accidental and deliberate, at least that Larry (and others, me for example) is perfectly happy with it: Perl behaves and evolves like a natural language (have you ever seen a formal definition of English? I haven't either). The fact that it is not designed a-priori allows for more room to evolve, with the community and the coders using p5p to solve problems when they arise and not beforehand. This process lets us find the best (for some value of best that takes into account DWIM and backwards compatibility) way to incorporate improvements to the language. Plus we can include new features without having necessarily sorted them out completely, and wait for user feedback to complete the implementation.
But I realize this can be unsettling for people used to reading the BNF of the language they use.