Looking at the generated JavaScript function, you're using Sun Mojarra as JSF implementation (please mention that with more detail in the future, you could for instance also have used Apache MyFaces).
I just tried the following SSCCE on Tomcat 6.0.20 with Mojarra 1.2_14:
<%@ taglib uri="http://java.sun.com/jsf/html" prefix="h"%>
<%@ taglib uri="http://java.sun.com/jsf/core" prefix="f"%>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<f:view>
<html>
<head>
<title>SO question 2111438</title>
</head>
<body>
<h:form id="form">
<h:commandLink id="link" value="link" action="#{bean.action}" target="_blank">
<f:param name="paramname" value="paramvalue" />
</h:commandLink>
</h:form>
</body>
</html>
</f:view>
...with a dummy action method on a request scoped bean and it just works flawlessly on Chrome 3.0.195.38.
I however recall similar JavaScript problem with Safari which has been fixed about around Mojarra 1.2_08. Ensure that you're using the latest Mojarra version. You can get it at their main dev site. Hope this helps.
The full generated HTML source was by the way (slightly reformatted):
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<title>SO question 2111438</title>
</head>
<body>
<form id="form" name="form" method="post" action="/playground/test.jsf" enctype="application/x-www-form-urlencoded">
<input type="hidden" name="form" value="form" />
<script type="text/javascript" language="Javascript">function dpf(f) {var adp = f.adp;if (adp != null) {for (var i = 0;i < adp.length;i++) {f.removeChild(adp[i]);}}};function apf(f, pvp) {var adp = new Array();f.adp = adp;var i = 0;for (k in pvp) {var p = document.createElement("input");p.type = "hidden";p.name = k;p.value = pvp[k];f.appendChild(p);adp[i++] = p;}};function jsfcljs(f, pvp, t) {apf(f, pvp);var ft = f.target;if (t) {f.target = t;}f.submit();f.target = ft;dpf(f);};</script>
<a id="form:link" href="#" onclick="if(typeof jsfcljs == 'function'){jsfcljs(document.getElementById('form'),{'form:link':'form:link','paramname':'paramvalue'},'_blank');}return false">link</a><input type="hidden" name="javax.faces.ViewState" id="javax.faces.ViewState" value="j_id8:j_id9" />
</form>
</body>
</html>