You can do that without an I/O redirection:
sed -i 's/$/\n/' filename
You can also use this command to append a newline to a list of files:
find dir -name filepattern | xargs sed -i 's/$/\n/' filename
For echo, some shells implement it as a shell builtin command. It might not accept the -e option. If you still want to use echo, try to find where the echo binary file is, using which echo. In most cases, it is located in /bin/echo, so you can use /bin/echo -e "\n" to echo a new line.