In Perl this algorithm is fine. The amortized cost of building up a string of length n in Perl is O(n) - a better approach can give you a constant factor improvement but nothing major.
Also .= should be the fastest way to append a byte to a scalar in native Perl. If it isn't, then it is not far from it. (I would regard anything else as a bug in Perl.)
However you are right to be concerned about the potential performance. In any of Python, Ruby, JavaScript, or Java your approach would scale as O(n*n) because their equivalents to .= actually create new strings rather than modifying an existing one in place. If you look around in these languages there is often an alternate data structure which is similar to a String, but which is designed for repeated appends. For instance in Java use a StringBuffer and .append to it. As a worst case you can actually write such a data structure. For a simple approach, use an array and then join it together when you need a string. (Simple, but you can do better - however that is OT.)
